一、01背包
请参考洛谷p1048采药
1.二维dp
二维dp
有 5 个药，花费时间分别是 [2,2,6,5,4]，价值分别是 [6,3,5,4,6]，时间限制为 10
状态转移方程
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
二重循环
for (int i = 0; i < n; i++) {
for (int j = t; j >= w[i]; j--) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
此时的 j 从t到w[i] 或者从w[i]到t ,都是一样的，从表中可以看出
j的遍历顺序没有影响
2.一维dp
为了减小空间采用一维数组
for (int i = 0; i < n; i++) {
for (int j = t; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
去掉dp中的[i]项，为了保证 dp[j] dp[j - w[i]] 都是i - 1上一项的，j 的循环顺序要从t到w[j]
3.记忆化搜索
较为简单，略
二、完全背包
每种药可以采无限次
1.二维dp
状态转移方程
01背包
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
完全背包
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
此时，取第i个药时还能再取第i个药，因此没有退回i-1
01背包中，不能再次取第i个，所以一定要退回i-1
二重循环
for (int i = 0; i < n; i++) {
for (int j = w[j]; j <= t; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}
}
此时j的遍历顺序只有一种，计算 dp[i][j] 时，要保证 dp[i][j - w[i]] 已经计算好，所以j必须从左到右遍历
2.一维dp
for (int i = 0; i < n; i++) {
for (int j = w[j]; j <= t; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
还是从左到右遍历，保证计算 dp[i][j] 时，dp[j] 是 i - 1 的，dp[j - w[i]] 是 i 的
3.其他
完全背包还有其他方法，略去（转换成01背包)
三、多重背包
每种药有一个采摘上限（01背包就是每种药都是1，完全背包这个上限是无穷大）
1.转化成01背包
略
2.其他
略
