正在查看旧版本。 查看 当前版本.
与当前比较 查看页面历史记录
« 前一个 版本 6 下一个 »
题目链接:2. 01背包问题 - AcWing题库
有N件物品和一个容量为V的背包,第i件物品的费用是c[i],价值是w[i],求将哪些物品装入背包可使总费用不超过背包的容量,且价值之和最大。
N
V
i
c[i]
w[i]
重点:每件物品仅有一件,可以取或不取。
定义F[i][v]表示将第i件物品放入一个容量为v的背包的价值,则其状态转移方程如下:
F[i][v]
v
F[i][v] = max{F[i-1][v], F[i-1][v-c[i]] + w[i]}
上面的这个方程的含义如下:
i-1
F[i-1][v]
v-c[i]
F[i-1][v-c[i]]
示例代码实现如下:
#define MAXN 1005 int n; // 物品数 int v; // 背包容量 int c[MAXN]; // 物品费用 int w[MAXN]; // 物品价值 int f[MAXN][MAXN]; // f[i][j],j体积下前i个物品的最大价值 int knapsack01() { cin >> n >> v; for(int i = 1; i <= n; i++) { // 下标从1开始 cin >> c[i] >> w[i]; } // 注意这里隐含设置了取0件物品和背包容量为0时f数组对应的值全为0的情况 // for(int i = 0; i <= v; i++) f[0][i] = 0; // for(int i = 0; i <= n; i++) f[i][0] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= v; j++) { if(j < c[i]) { // 当前背包容量j装不下第i个物品,则价值等于前i-1个物品 f[i][j] = f[i-1][j]; } else { // 能装,按方程进行决策 // 注意,当到j恰好能装下全部的前i件物品时, // 后续的j可直接设置成f[i][j-1],因为后续的j表示背包容量已经有冗余了 f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + w[i]); } } } return f[n][v]; }
根据状态转移方程可知,第i件物品的计算过程只与第i-1件物品有关,由于可以想到使用滚动数组的方式,将空间复杂度降为从二维降至一维。
f[j]
j
0
为什么采用逆序,参考以下解释:
状态方程:dp[j] = max(dp[j], dp[j - v[i]] + w[i])
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
假如枚举到:i = 3, j = 8, v[3] = 5, w[3] = 1
i = 3, j = 8, v[3] = 5, w[3] = 1
二维:dp[3][8] = max(dp[2][8], dp[2][3] + w[3]) 此时的dp[2][8]和dp[2][3]都是上一轮的状态值
dp[3][8] = max(dp[2][8], dp[2][3] + w[3])
dp[2][8]
dp[2][3]
一维:dp[8] = max(dp[8], dp[3] + w[3]) 我们要保证dp[8]和dp[3]都是上一轮的状态值
dp[8] = max(dp[8], dp[3] + w[3])
dp[8]
dp[3]
按照逆序的顺序,一维dp数组的更新顺序为:dp[8], dp[7], dp[6], ... , dp[3]
dp
dp[8], dp[7], dp[6], ... , dp[3]
也就是说,在本轮更新的值,不会影响本轮中其他未更新的值!较小的index对应的状态是上一轮的状态值!
index
如果按照顺序进行更新,dp[3] = max(dp[3], dp[0] + w[0]),对dp[3]的状态进行了更新,那么在更新dp[8]时,用到的dp[3]就不是上一轮的状态了,不满足动态规划的要求。
dp[3] = max(dp[3], dp[0] + w[0])
简单来说,如果从小到大更新j,则先更新dp[3],后面再更新dp[8]时会用到已经更新过的dp[3],而不是上一轮的dp[3],而如果按从大到小更新j,则先更新dp[8],此时用到的dp[3]还是上一轮的dp[3]。由于dp[j]的更新依赖于dp[j-v[i]],这就需要保证在更新dp[j]时,所有比j小的dp都是未更新过的。
dp[j]
dp[j-v[i]]
示例代码:
#define MAXN 1005 int n; // 物品数 int v; // 背包容量 int c[MAXN]; // 物品费用 int w[MAXN]; // 物品价值 int f[MAXN]; // f[j],j体积下前N个物品的最大价值 int knapsack01() { cin >> n >> v; for(int i = 1; i <= n; i++) { // 下标从1开始 cin >> c[i] >> w[i]; } for(int i = 1; i <= n; i++) { for(int j = v; j >= 0; j--) { if(j < c[i]) { f[j] = f[j]; // 这里左边的是第i轮的f[j],右边的是第i-1轮的f[j] } else { f[j] = max(f[j], f[j - c[i]] + w[i]); } } } return f[v]; }
以上代码的循环部分可进一步简化:
for(int i = 1; i <= n; i++) { for(int j = v; j >= c[i]; j--) { f[j] = max(f[j], f[j - c[i]] + w[i]); } }
可以转化成在线处理输入的方式,而不必开两个数组来保存c和w,如下:
c
w
#include <iostream> using namespace std; #define MAXN 1005 int f[MAXN]; int main() { int n, v; cin >> n >> v; for(int i = 1; i <= n; i++) { int c, w; cin >> c >> w; for(int j = v; j >= c; j--) { f[j] = max(f[j], f[j - c] + w); } } cout << f[v]; }