版本比较
标识
- 该行被添加。
- 该行被删除。
- 格式已经改变。
01背包
题目链接:2. 01背包问题 - AcWing题库
有N
件物品和一个容量为V
的背包,第i
件物品的费用是c[i]
,价值是w[i]
,求将哪些物品装入背包可使总费用不超过背包的容量,且价值之和最大。
重点:每件物品仅有一件,可以取或不取。解题思路:
朴素解法
定义F[i][v]
表示将第i
件物品放入一个容量为v
的背包的价值,则其状态转移方程如下:
F[i][v] = max{F[i-1][v], F[i-1][v-c[i]] + w[i]}
上面的这个方程的含义如下:
- 将第
i
件物品放入容量为v
的背包的最大价值,只需要考虑第i
件物品是否放入背包,有放和不放两种情况。 - 如果不放第
i
件物品,那么总价值就是前i-1
件物品放入容量为v
的背包的价值,也就是F[i-1][v]
。 - 如果放入第
i
件物品,那么就价值就是第i
件物品的价值w[i]
,加上前i-1
件物品放入容量为v-c[i]
的背包的价值F[i-1][v-c[i]]
。 - 以上两者取最大值,即为第
i
件物品放入容量为v
的背包的最大价值。
示例代码实现如下:
代码块 |
---|
#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]
,表示N
件物品在背包容量为j
下的最优解。 - 枚举容量,
j
必须从V
枚举到0
,也就是逆序。 为什么采用逆序,参考以下解释:
代码块tip 状态方程:
dp[j]
=
max(dp[j],
dp[j
-
v[i]]
+
假如枚举到:i =w[i])
假如枚举到:
i = 3,
j
=
8,
v[3]
=
5,
w[3]
1 二维:dp=
1
二维:
dp[3][8]
=
max(dp[2][8],
dp[2][3]
+
此时的dpw[3])
此时的
和dpdp[2][8]
和
一维:dpdp[2][3]
都是上一轮的状态值一维:
dp[8]
=
max(dp[8],
dp[3]
+
我们要保证dpw[3])
我们要保证
和dpdp[8]
和
按照逆序的顺序,一维dp数组的更新顺序为:dpdp[3]
都是上一轮的状态值按照逆序的顺序,一维
dp
数组的更新顺序为:dp[8],
dp[7],
dp[6],
...
,
也就是说,在本轮更新的值,不会影响本轮中其他未更新的值!较小的index对应的状态是上一轮的状态值! 如果按照顺序进行更新,dpdp[3]
也就是说,在本轮更新的值,不会影响本轮中其他未更新的值!较小的
index
对应的状态是上一轮的状态值!如果按照顺序进行更新,
dp[3]
=
max(dp[3],
dp[0]
+
,对dpw[0])
,对
的状态进行了更新,那么在更新dpdp[3]
的状态进行了更新,那么在更新
时,用到的dpdp[8]
时,用到的
dp[3]
就不是上一轮的状态了,不满足动态规划的要求。
作者:polaris 链接:https作者:polaris
链接:https://www.acwing.com/solution/content/3982/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。简单来说,如果从小到大更新
j
,则先更新dp[3]
,后面再更新dp[8]
时会用到已经更新过的dp[3]
,而不是上一轮的dp[3]
,而如果按从大到小更新j
,则先更新dp[8]
,此时用到的dp[3]
还是上一轮的dp[3]
。
示例代码:
代码块 |
---|
#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
,如下:
代码块 |
---|
#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];
} |
目录 |
---|