书上没有的动态规划例题,有详解,有填表过程
时间: 2023-12-05 15:20:16 浏览: 27
这是一个使用动态规划算法解决「背包问题」的变种问题,称为 「多重背包问题」,每个物品可以选择放入多次,但总重量不能超过背包容量的例题:
问题描述:有 $n$ 种物品和一个容量为 $m$ 的背包。第 $i$ 种物品的重量是 $w_i$,价值是 $v_i$,每种物品有 $c_i$ 个,其中第 $i$ 种物品最多可以选 $c_i$ 个,求解将哪些物品装入背包可使这些物品的总重量不超过背包容量,且总价值最大。输出最大价值。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100;
int n, m;
int w[MAXN], v[MAXN], c[MAXN];
int dp[MAXN][MAXN]; // dp[i][j] 表示前 i 种物品,总重量不超过 j 的情况下的最大价值
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i] >> c[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= c[i] && k * w[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
```
在多重背包问题中,同一种物品可以选择放入多次,因此状态转移方程需要进行修改。设 $dp[i][j]$ 表示前 $i$ 种物品,总重量不超过 $j$ 的情况下的最大价值,则状态转移方程为:
$$
dp[i][j]=\max_{0\leq k\leq c_i}\{dp[i-1][j-kw_i]+kv_i\}
$$
其中 $k$ 表示第 $i$ 种物品选择的个数,$w_i$ 和 $v_i$ 分别表示第 $i$ 种物品的重量和价值,$c_i$ 表示第 $i$ 种物品的最大数量。为了避免重复计算,第 $i$ 种物品最多只能选择 $c_i$ 个,而且 $k\times w_i\leq j$,即选择的物品总重量不能超过背包容量。最终,$dp[n][m]$ 即为所求的最大价值。