当前位置：首页 > news >正文

动态规划（6）——01背包问题

news 来源：原创 2025/9/11 11:18:10

欢迎来到博主的专栏：算法解析
博主ID：代码小号

文章目录

- 牛客网——【模板】01背包
- - 题目解析
  - 题目1算法原理
  - 题目1题解代码。
  - 问题2算法原理
  - 问题2题解代码
  - 01背包问题的滚动数组优化

牛客网——【模板】01背包

题目解析

在这里插入图片描述
关于I/O相关的东西博主就不多赘述了，我们以示例1为例，当前地上有3个物体，背包的体积只有5。物体1的体积是2，价值为10，物体2的体积是4，价值为5，物体3的体积是1，价值为4。（1）要求我们在不超过背包体积的情况下，装下的物体的最大价值。（2）要求我们求出当背包正好装满时，能装下的最大价值。
在这里插入图片描述

对于问题1，由于我们要尽可能的追求最大价值，因此只要背包能装下东西就一定要装下：示例1有下面两种方案。选择价值最大的方案
在这里插入图片描述

对于问题2，只有一种方案能让背包装满，因此虽然价值不是最大的，但是依旧是最终答案
在这里插入图片描述

题目1算法原理

对于问题1，我们要抽象出背包问题的两个重要属性。1、可挑选的物品有限制，2、要求挑选出物品的最大价值，那么我们的状态表示就要涵盖这两个方面。

我们将物品进行从1开始编号，如下
在这里插入图片描述
我们规定，dp[i][j]表示：在[1,i]号物品中进行挑选，物体的总体积不超过j的最大价值。为什么要假设是这个状态表示？首先根据上面的分析，我们知道状态表示要涵盖对选取物体的限制，同时也要确定最大价值，其二则是根据题目要求，题目要求我们在n个物品中挑选体积不超过背包体积的最大价值，而正好我们的状态表示符合这个要求。

那么如何判断我们的状态表示正确与否呢？我们可以先尝试用这个状态表示来推导一下状态转移方程，如果状态转移方程推导的不是很顺利。那么就要尝试更换一个状态表示了。

回到dp[i][j]的状态表示。在[1,i]中挑选物品，对于每一个i，可以将所有的可能的情况分成两种，一种是不将物体i装进背包的情况，一种是将物体i装进背包的情况。

我们根据这两个情况推导状态专题方程。
在这里插入图片描述
如果我们选择不将i装入背包，那么此时我们就要在剩下的物品中，挑选总体积不超过j的多个物品，但是我们由于我们的dp[i][j]需要求的是最大值，那么也就说明，在剩下的物品中挑选总体积不超过j的情况，也必须是最大价值，即dp[i-1][j]。那么此时dp[i][j]=dp[i-1][j]。

如果我们将第i个物体放入背包，那么为了追求最大价值，我们需要在[1,i-1]当中挑选剩下的物品，但是，由于此时背包当中已经放入一个i了，那么剩下的可容纳体积则是j-v[i]。因此该情况下的dp[i][j]=dp[i-1][j-v[i]]+w[i]。由于我们要求出的是最大值，因此状态转移方程如下：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])。但是要注意下标的问题，j-v[i]是可能小于0的，因此只有j-v[i]<=0的时候，我们就认为dp[i-1][j-v[i]]+w[i]的值为0。

在这里插入图片描述

接下来就是初始化问题，由于状态转移方程涉及i-1这个操作，因此我们不能让i=0，因此我们要对其进行初始化。

如果i0,j0,则说明在0个物体当中挑选体积不超过0的最大价值，由于此时没有物体可选，因此背包价值为0，即dp[0][0]=0
如果i=0,j>0,则说明在0个物体当中挑选体积不超过j的最大价值，同样的没有物体可选，因此背包价值为0.dp[0][j]=0

由于题目中会输入n个物体，因此v[i]和w[i]的下标是[0,n-1]范围内，但是我们的dp表的返回值是dp[n][V]。即表示在n个物体当中组合出体积不超过V的最大价值。所以dp表的是一个(n+1)*（V+1）大小的数组。此时我们要注意dp表的状态转移方程与v[i]和w[i]的下标映射关系。即：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])

题目1题解代码。

int main() {int n,V;cin>>n>>V;vector<int> v(n);//物体体积表vector<int> w(n);//物体价格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<vector<int>> dp(n+1,vector<int>(V+1));for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//不选i的情况下的最大值if(j-v[i-1]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//选i情况下的最大值，前提是合法}}cout<<dp[n][V]<<endl;
}

问题2算法原理

由于问题2要求是在装满背包的情况下，装取物品的最大价值。那么我们就可以将状态表示修改一下：dp[i][j]表示，在前i个物品当中进行挑选，当挑选的物品恰好总体积为J时，背包的最大价值。

那么我们可以开始推导状态转移方程了，对于任意i，我们可以将所有的可能的枚举情况，分成两种，一种是选择i的情况，一种是不选i的情况。因此我们需要推导出这两种情况下dp[i][j]的最大值。

对于不选i的情况，此时我们可以在剩下的i-1个物品中挑选恰好体积等于j的最大值，那么这段描述不是符合dp[i-1][j]的状态表示？因此状态转移方程为：dp[i-1][j]。

对于选i的情况，此时由于物品i已经被选进背包了，此时背包容量只剩j-v[i]。物品还剩下i-1个可以挑选，因此我们需要在剩下的i-1个物品进行挑选，使其总体积恰好为j-v[i]的情况下的最大价值，那么这段描述的状态表示就是dp[i-1][j-v[i]]。由于物品i已经被选上了，因此选i的背包价值为： dp[i][j]=dp[j-v[i]]+w[i]。

但是有一个问题出现了，如果dp[i-1][j-v[i]]有没有可能不存在？当然是有可能的，因为剩下的i-1个物体很有可能怎么凑，都凑不出j-v[i]这个体积，那么相应的，dp[i][j]的值也就不存在了。那么我们就要思考一个问题了，对于非法的状态表示（即无法凑满总体积为j的物品）,该用什么值来表示呢？有人说既然背包没有东西，那不就是没有价值。因此用0来表示。但是我们再思考一下，0这个值一定是非法的吗？在前面讨论初始化的时候，博主是不是说过，当i0时，j0时，此时有0个物体可挑选，需要让挑选物品的总体积恰好为0。这个状态明明是合法的，而且由于此时什么也没挑，因此背包的最大价值为0，因此0不是非法状态下的取值。我们可以使用-1来表示非法状态下的表示。

因此状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])(dp[i-1][j-v[i]]合法的情况下(不为-1))。

接下来就是初始化的问题，i0时，j0时合法，因此背包价值为0，dp[0][0]=0.当i==0，j>0时，此时无法凑成总体积恰好为j的情况，因此是非法的情况，即dp[0][j]=-1。那么最后一个细节就是体积表和价值表与dp表之间的映射问题了。

问题2题解代码

#include <iostream>
#include <vector>
using namespace std;int main() {int n,V;cin>>n>>V;vector<int> v(n);//物体体积表vector<int> w(n);//物体价格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<vector<int>> dp(n+1,vector<int>(V+1));for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//不选i的情况下的最大值if(j-v[i-1]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//选i情况下的最大值，前提是合法}}cout<<dp[n][V]<<endl;//问题1的结果dp.resize(n+1,vector<int>(V+1));//重新复用一下dp表for(int j=1;j<V+1;j++) dp[0][j]=-1;for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//选i且合法的情况if(j-v[i-1]>=0&&dp[i-1][j-v[i-1]]!=-1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//}}cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;//问题2的结果
}

01背包问题的滚动数组优化

根据状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);对于任意一个位置的dp[i][j]，其取值返回都只在上一行当中。
在这里插入图片描述
（写到这里博主的截图工具有点用不了了，但是又是因为在学校机房写的，因此不想关机重写hh，那就用截图键凑合看吧）

我们可以看到实际上只需要两行的数组，只要下面一行填完了，就让下面一行去作为上面一行继续更新。那么就可以实现空间优化。
在这里插入图片描述
实际上这个工作只需要一行数组就能完成。如下：

由于我们对于任意一个dp[i][j]，我们都只会用到上一行，以及上一行当中左边的某一个值。因此如果我们之开一行数组，然后从右往左遍历dp。这样dp表就可以仅使用一维的情况下，完成整个过程，节省了空间开销。

代码如下：

#include <iostream>
#include <vector>
using namespace std;int main() {int n,V;cin>>n>>V;vector<int> v(n);//物体体积表vector<int> w(n);//物体价格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<int> dp(V+1);//只需要一行dpfor(int i=1;i<n+1;i++){//注意虽然dp表只有一行，但是状态转移方程并没有改变，因此i不能删除for(int j=V;j>=v[i-1];j--){dp[j]=max(dp[j],dp[j-v[i-1]]+w[i-1]);//选i情况下的最大值，前提是合法}}cout<<dp[V]<<endl;//问题1的结果dp.resize(V+1);//重新复用一下dp表for(int j=1;j<V+1;j++) dp[j]=-1;for(int i=1;i<n+1;i++){for(int j=V;j>=v[i-1];j--){//选i且合法的情况if(dp[j-v[i-1]]!=-1) dp[j]=max(dp[j],dp[j-v[i-1]]+w[i-1]);//}}cout<<(dp[V]==-1?0:dp[V])<<endl;//问题2的结果
}