完全背包
有N种物品和一个容量为V的背包，每种物品都有无限件可用。 第i种物品的费用是c[i]，价值是w[i]。 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。python
为了方便，我就拿上面力扣的题说了。正常情况下dp方程如下：
f[i][j]表示第i个硬币，凑齐j元时花费的最少硬币数
转移方程为：
f[i][j] = min(f[i - 1][j], f[i][j - coin[i] * k] + k)
可以发现用这个转移方程需要三层遍历(分别枚举i、j和k)，正常情况肯定是会直接T掉的。
但是仔细观察一下可以发现，k其实没必要遍历，来看一下下面这个转移方程：
f[i][j] = min(f[i - 1][j], f[i][j - coin[i]] + 1)
可能还看不出来，我们把它套进循环里：
for (int i = 1; i <= coins.length; i++) {
int last = i - 1;
int coin = coins[last];
for (int j = 1; j <= amount; j++) {
int val = j >= coin ? f[i][j - coin] + 1 : Integer.MAX_VALUE;
f[i][j] = Math.min(f[last][j], val);
}
}
java
有没有那种感觉了？我们枚举k会导致很大一部分被重复计算了！
当然，这个dp方程可以把i这一纬给优化掉，而且还不需要倒着遍历。
多重背包
多重背包需要和完全背包区分，多重背包是每个物品只能选有限个，而完全背包则是无限个
完全背包的题目可以使用多重背包来解，不过一般会超时？
P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题如果暴力dp，那么转移方程和上面完全背包差不多，也是三重遍历：
for (int i = 1; i <= n; ++i) {
for (int j = maxWeight; j >= w[i]; --j) {
for (int k = 1; k <= m[i]; ++k) {
int last = j - k * w[i];
if (last < 0) {
break;
}
f[j] = max(f[j], f[last] + k * v[i]);
}
}
}
java