个人主页 ： zxctscl
如有转载请先通知
DP41 【模板】01背包
- 1. DP41 【模板】01背包
- 2. 分析
- 3. 代码
- 4. 优化
- 5. 优化后代码
1. DP41 【模板】01背包
2. 分析
一、题目解析：
来看一下例1，3代表有三个物品，5代表能够容纳的体积。第一行要求中并没有说把背包全部装满，选择价值最大的就行，而第二行输出要求的是装满时候的价值。
在体积是5条件下，第一种可以选1号物品和3号物品，它们价值就是10+4=14；第二种可以选择2号和3号，它们价值就是5+4=9，第一行输出没有要求背包装满，所以选择第一种方式就行。
第二行输出是背包恰好装满的情况，就选择第二种情况。
而输出背包必须装满的情况可能是不存在的，就像例2：
给的三个物品体积凑不出来体积为8的情况。
二、算法原理：
（1）先来做第一行返回值：
-
状态表示
以某一个位置为结尾
如果用dp[i]来表示从前i个物品中选择，在所有选择中的最大价值，但是还得考虑体积的大小。所以这里的状态表示是：
dp[i][j]：从从前i个物品中选择，总体积不超过j的所有选择中，能挑出来的最大价值。 -
状态转移方程
根据最后一步的状况，分情况讨论。
第一种情况：不选择i物品，那么就是在i-1里面选择，并且体积也依旧小于j,所以就是dp[i-1][j]
第二种情况：选择i物品，那么必须有w[i]，实现的价值最大，就得从i-1里面挑价值最大的出来，并且此时体积要改变，所以到这里的体积必须能够装下v[i]，到i-1位置体积就必须小于j-v[i]，所以这里的状态表示就是w[i]+dp[i-1][j-v[i]]
然后求这两种情况下的最大值就可以了。
-
初始化
dp表从1开始计数，就多了一行和一列。要保证第一行和第一列填表正确，物品从0中选就是0，体积从0中挑还是0，所以初始化为0就行。 -
填表顺序
它依赖它的上一行位置，i-1表示的是上一行，从上往下 -
返回值
返回dp[n][v]
（2）先来做第一行返回值：
-
状态表示
只需要v的位置正好等于j就行
dp[i][j]：从从前i个物品中选择，总体积正好等于j的所有选择中，能挑出来的最大价值。 -
状态转移方程
第一种情况：不选择i物品，那么就是在i-1里面选择，并且体积也依旧小于j,所以就是dp[i-1][j]，但是这里j可能凑不到总体积，就用一个dp[i][j]=-1来表示这样的情况，所以得先判断dp[i][j]是不是等于-1，所以这种情况就不选择。
第二种情况：选择i物品，那么必须有w[i]，实现的价值最大，就得从i-1里面挑价值最大的出来，并且此时体积要改变，所以到这里的体积必须能够装下v[i]，到i-1位置体积就必须小于j-v[i]，但是这里必须判断dp[i][j]是不是等于-1，所以这里的状态表示就是dp[i][j]不是等于-1情况下w[i]+dp[i-1][j-v[i]]
-
初始化
第一个位置没有物品直接物品和体积都是0,第一行[0,1]位置没有物品，想要凑成体积是1是不可能的，所以第一行剩下的位置就初始化为-1。第一列表示想要把体积正好凑成0，那么不选就是0，就初始化为0就行
-
填表顺序
从上往下 -
返回值
先得判断一下dp[n][V]是不是等于-1，如果是就返回0，不是就返回dp[n][V]
3. 代码
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N][N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
cout << dp[n][V] << endl;
//第二问
memset(dp, 0, sizeof dp);
for (int j = 1; j <= V; j++)dp[0][j] = -1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i]&&dp[i-1][j-v[i]]!=-1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout <<(dp[n][V]==-1?0:dp[n][V]) << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
4. 优化
- 利用滚动数组做空间上的优化
- 代码在原基础上修改即可
在填第i行的时候，仅想要i-1行就可以。
就是说要填第1行的数据就需要第0行的数据，第1行填完之后，第0行就没有用了，需要这一行变得有用，就把这一行滚动到第2行，然后利用第1行的值来填第2行，以此类推，就可以更新完这个dp表。
所有这里只需要用到数组就只用到一维。
遍历顺序要改为从右往左。
5. 优化后代码
删除所有横坐标，遍历顺序从右往左
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp[N];
int main() {
cin >> n >> V;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = V; j >=v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
cout << dp[V] << endl;
//第二问
memset(dp, 0, sizeof dp);
for (int j = 1; j <= V; j++)dp[j] = -1;
for (int i = 1; i <= n; i++) {
for (int j = V; j >=v[i]; j--)
if(dp[j-v[i]]!=-1)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
cout <<(dp[V]==-1?0:dp[V]) << endl;
return 0;
}
// 64 位输出请用 printf("%lld")
注意：
- 这些思路是可以套用到很多题目里面的。
- 不要去强行解释优化后代码的状态表示及状态表示方程。
有问题请指出，大家一起进步！！！
