【动态规划】01背包问题
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1. 背包问题
背包问题 (Knapsack problem) 是⼀种组合优化的 NP完全问题
问题可以描述为：
你有一个背包，地上有一堆物品，挑选一些物品放入背包中。
问：最大能挑选出来的价值是多少？
如果就题目就这么简单，也太简单了，直接把所有物品都放背包里就行了。事情其实并没有这么简单。每个物品都有限定条件，比如说
- 物品的属性
- 背包的属性
物品编号从1开始，属性有价值、体积、还有个数，个数涉及背包问题的分类。
如果每个物品都有体积的话，那这个背包就有一个容量属性，假设是6。
所以说，不是把所有物品都放在背包里，而是只能挑选出一些放到背包里。
下面这几乎所有背包都是这样问的，你有一个背包有一个限制条件，然后把这些物品放到限制条件里，问最大能挑选出来的价值是多少？
然后根据 物品的个数，可以把背包分为若干类。
所有物品都只有一个，从这几个物品里面挑一些物品放到背包里，问最大能挑选出来价值是多少。这个问题我们称为01背包。为什么叫01背包，很简单，挑了某个物品这个物品就有一个，如果没挑，就只有0个。每个物品都面临选or不选两种情况，选了就是1，没选就是0。
所有物品都有∞个，可以在容量限制下，一直拿某个物品。问最大能挑选出来价值是多少。这个问题我们称为完全背包。
当然还有其他物品个数分类的情况：
- 多重背包问题：每件物品最多有 si 个
- 混合背包问题：每个物品会有上面三种情况…
- 分组背包问题：物品有 n 组，每组物品里有若干个，每组里最多选⼀个物品
我们重点就研究01背包，完全背包问题。
其中上述分类里面，根据背包是否装满，又分为两类：
- 不必装满
- 必须装满
像这里就有四种组合了，比如01背包里面，它会问，不必装满最大价值是多少。必须装满最大价值是多少。
01背包问题是所有背包问题的基础！
2. 01背包
题目链接： DP41 【模板】01背包
题目分析：
第一问问的是背包不必要装满最大价值是多少。
第二问问的是背包必须装满最大价值是多少。
示例2，第二问，如果没有满足背包必须装满的情况，输出0
算法原理：
先解决第一问，背包不一定装满的情况：
1.状态表示
其实这个背包问题是一个线性dp问题，因为挑选物品的时候我们可以从左往右挑选。选或者不选这个物品。
线性dp，老套路了。继续根据 经验 + 题目要求
根据最后一个位置，结合题目要求，来定义一个状态表示。
如果是最后一个位置，相当于就是从编号1号物品挑到 i 号物品，也就是从前 i 个物品中挑选，要挑选出的最大价值。
dp[i] 表示：从前 i 个物品中选，所有选法中，能挑选出来的最大价值。
但是这个状态表示，推导不出来状态转移方程。推导 dp[i] 的时候可能要用到 i 之前的状态，也就是说求这个dp[i] 的时候会考虑这个 i 号物品选or不选，如果 i 号物品要选，那必须要保证背包要有容量能放下 i 号物品的体积。但是这个dp[i] 并不知道容量的信息。也就是说我要选 i 号物品的时候，根本就不知道背包此时的容量还有多少，我怎么能把 i 号物品放进去呢？因此上面一维状态表示推到不出来状态转移方程。
刚才状态表示没有体积这个条件，所以说，接下来我们把体积添加到状态表示：
dp[i][j] 表示：从前 i 个物品中选，总体积不超过 j，所有选法中，能挑选出来的最大价值。
2.状态转移方程
根据最后一步的状况，分情况讨论
从1号物品挑到 i 号物品，要么选择 i 号物品，要么不选 i 号物品。
不选 i 号物品，前面所有选法中，最后一个位置都不选 i 物品，是不是只去 1 ~ i - 1 号物品去挑，并且总体积依旧不等于 j，正好我们的状态表示就是从某个区间去挑，总体积不超过某个数，能跳的最大价值。
选 i 物品，所有选法中，最后一个位置一定选 i 物品，那肯定会有一个w[i]表示 i 号物品的价值，接下来去 1 ~ i - 1物品挑一个最大价值不就行了，但是此时的体积就不在是 j 了。因为挑到 i 号物品的时候总体积要求不超过 j ，那选了 i 号物品，然后从1 ~ i - 1物品选是不是要剩下一点体积能让我挑选 i 号物品啊，剩多少呢？ j - v[i]。也就是说选了 i 号物品，接下来去1 ~ i - 1物品选总体积不超过j - v[i]最大价值，那正好在 dp[i-1][j-v[i]]里存着。
这里需要多考虑一点，j - v[i] 不一定存在。比如说挑选到 i 号物品的时候总体积要求不超过1，但是第 i 号物品的体积就已经等于5了。那怎么也装不下。那选 i 号物品这种情况就相当于不存在。如果想选 i 号物品这种情况存在，那 j - v[i]必须要有剩余空间。
然后我们取这两种情况的最大值就可以了
3.初始化
物品是从1开始的，也就是从数据下标1开始。相当于dp表天然多了一行多了一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一行 i 等于0，表示从0号物品中选，但是我们没有0号物品，我们物品编号是从1开始的。i = 0相当于没有物品，如果没有物品，想凑成容量不超 j 根本不可能做到。
第一列表示 j 等于0，表示容量不超过0，但是物品总数有体积的，但是我不选不就可以了吗
4.填表顺序
填dp[i][j]依赖dp[i-1][…]，也就是填 i 行 依赖于 i- 1行。所以从上往下填。
5.返回值
dp[i][j] 表示：从前 i 个物品中选，总体积不超过 j，所有选法中，能挑选出来的最大价值。这道题第一问这个背包至多能装多大价值的物品? 也就是背包装的体积小于V即可。所以我们应该从前n个物品中选，总体积不超过 V，所有选法中，能挑选出来的最大价值。所以返回的是dp[n][V]
截止到目前为止，第一问我们就分析完了。接下来我们再看第二问，背包恰好装满，求至多能装多大价值的物品？
第二问仅仅在分析稍加修改即可。无非就修改几点就行了。
1.状态表示
2.状态转移方程
接下来状态转移方程一模一样，但是需注意的是：
dp[i-1][j] 一定存在吗？dp[i-1][j] 意思是 从前 i - 1个物品中选，总体积正好等于 j。但是我们不一定就能选到。如果凑不到 j，里面值应该是多少呢？这里我们做个约定，如果 dp[i][j] == -1 表示没有这种情况，总体积凑不出 j。为啥这里不用 dp[i][j] == 0，如果用dp[i][j] == 0，你就会发现待会和填表哪里上面多开一行，左边多开一列哪里的dp[0][0]用一样的值很奇怪，哪里的dp[0][0]表示没有物品选总体积等于j，其实是可以选到的，但是里面价值等于0。如果把里面都定义成0，那选不出来这种情况就无法表示了。所以这里用dp[i][j] == -1 表示没有这种情况，总体积凑不出 j。
所以我们在用每一个状态之前都要判断状态存不存在，然后才能使用前面的状态。
比如不选 i 物品，要判断 dp[i-1][j] != -1，然后在使用这个状态。
但是其实 不选 i 物品，这里可以不考虑这个判断条件。因为不选 i 物品这种情况是一定存在的。所以说 dp[i][j] 可以先等于 dp[i-1][j]，如果dp[i-1][j] == -1，那没事dp[i-1][j] == -1，dp[i][j]也等于 -1。你选不了我也选不了。你从前 i - 1 个物品选想凑不出一个j，我这是不选 i 物品依旧凑不出j。所以第一种情况可以不用判断。
第二种情况选 i 物品，就需要考虑了。当 j - v[i] >= 0 想用 dp[i-1][j-v[i]]，就必须要dp[i-1][j-v[i]] != -1 存在。为什么这里需要判断，因为这里加了一个w[i]，如果dp[i-1][j-v[i]] == -1，两个加起来然后和第一种情况求max肯定会出错。
3.初始化
00位置和之前一样，没有物品，正好凑成0，那啥也不选就行了
第一行剩下的是，没有物品但是想凑成体积巧合等于 j 的，根本不可能做到。
第一列剩下表示想把体积恰好凑成0，那我不选物品就好了，那价值就是0
4.填表顺序
和第一问一样，从上往下填。
5.返回值
和第一问一样，返回的是dp[n][V]
#include <iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, V,v[N],w[N];
int dp[N][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 = 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;
}
优化
- 利用滚动数组做空间上的优化
- 直接在原始代码上稍加修改即可
首先我们先了解什么是滚动数组。
我们上面 dp[i][j] 依赖 dp[i-1][j] 和 dp[i-1][j-v[i]] 这两个位置的值。也就是 i -1行的这两个值，在上面的都不需要了。
像这种填ij位置的值，只需要上面i-1的状态，我们就可以用滚动数组。
滚动数组就是，仅需两个数组就可以完成上面所有的填表工作。具体怎么完成。先建立两个数组，刚开始第一个数组代表原始数组的第0行，第二个数组代表原始数组的第1行。接下来第0行初始化完成之后，然后填第1行的值。而我们填第1行的值仅依赖第0行的值就可以完成第1行的填表了。
填完之后，第0行就没有用了。没有用的话，我们可以让它变得有用。如何有用？我们让它滚下去，变成第2行。接下来填第2行的时候，仅需第1行的值。
同理填完第2行，第1行就没有用了。第1行就滚下去，变成第3行。。。这样交替往下滚动的过程就可以把原dp表填写完。这就是滚动数组。
如果我们发现填写这一行的状态全都是依赖上一行的话，就可以用滚动数组。不过这是最原始的滚动数组，利用两个数组来做滚动。
但是我们这里不说这个。利用两个数组做滚动数组感觉还是浪费空空间。甚至可以用一个数组就可以完成滚动过程。
一个数组如何写我们的状态转移方程呢？
一个数组实际上我们填的是 j 这个下标。也就是说一个数组的话 i 是不存在的。仅需填 dp [j]
当填 j 这个位置的时候，是不是需要知道上一行的三角，以及 j - v[i] 的三角。而上一行的三角正好在 dp[j] 存在， j - v[i] 的三角在 dp[j - v[i]] 存着。
但是这里有一个非常致命的问题，如果选择从左往右填表。之前 dp [j - v[i]] 位置的值是三角，但是填表的时候就会把这个位置的值更新变成圆圈。这个时候填 j 位置的时候就找不到dp [j - v[i]]的三角了。
我们要的是用完之后在更新。所以从左往右会把三角改变，那就从右往左填表。这样填 j 位置，j - v[i] 的值就没有改变。
滚动数组优化就这么一点变化，把 i 全部干掉，然后遍历顺序从右往左。
那我们如何在原始代码修改成滚动数组的优化呢？
- 删除所有的横坐标
- 修改一下 j 的遍历顺序
#include <iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int n, V,v[N],w[N];
//int dp[N][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 = 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;
//优化
// 解决第一问
for(int i = 1; i <= n; ++i)
for(int j = V; j >= v[i]; --j)//修改遍历顺序,并且这里第一次遇到j < v[i]情况,后面就不需要考虑了，所有把if(j >= v[i]) 放在循环上
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;
}
这里不仅空间优化，而且时间也优化了。就是因为 j 的遍历顺序，我们把之前 if 判断条件放到了循环里面，这样就少了很多情况。时间上有常数级别的提升。但是整体时间复杂度依旧是O(N^2)
原文地址：https://blog.csdn.net/fight_p/article/details/141494467
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！