devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划:01背包问题全解_01背包动态规划

作者：繁依Fanyi0 | 2024-03-29 01:51:51

赞

踩

01背包动态规划

01背包

一、前言

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

这是最标准的01背包问题，以至于我们有时看到了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。

这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O（n*n），这里的n表示物品数量。由于时间复杂度过高，我们才会想到用动态规划来解决这一系列问题

二、动态规划思想

1.确定dp数组及其下标含义

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

2.确定递推公式

让我们再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。由此我们可以根据一下两个方向来确定递推公式：

不放物品i:此时dp[i][j]=dp[i-1][j]，我们的dp含义已经是最大价值总和了，此时如果不选物品i，那么在背包容量为j的情况下挑选前i件物品的最大价值就等于在背包容量为j的情况下挑选前i-1件物品

放物品i：此时dp[i][j]=dp[i-1][j-weight[i]]+value[i]，选择物品i后背包容量为j，那么在没选物品i时，相当于以j-weight[i]这一背包容量在前i-1件物品中挑取的最大价值，并加上i的价值

综上所述，因为我们要做出选当前物品和不选当前物品中价值最大的那一步选择，所以最后确定的递推公式为：

 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 

3.初始化

首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。

当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

  1. // 初始化 dp
  2. vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
  3. for (int j = weight[0]; j <= bagweight; j++) {
  4.     dp[0][j] = value[0];
  5. }

4.确定遍历顺序

遍历分为两种，一种是先遍历背包，后遍历物品，另外一种是先遍历物品，后遍历背包。在01背包中先遍历背包和先遍历物品都是可以的

先遍历物品，后遍历背包

  1. // weight数组的大小 就是物品个数
  2. for(int i = 1; i < weight.size(); i++) { // 遍历物品
  3.     for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  4.         if (j < weight[i]) dp[i][j] = dp[i - 1][j];
  5.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  6.     }
  7. }

 先遍历背包，后遍历物品

  1. // weight数组的大小 就是物品个数
  2. for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
  3.     for(int i = 1; i < weight.size(); i++) { // 遍历物品
  4.         if (j < weight[i]) dp[i][j] = dp[i - 1][j];
  5.         else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  6.     }
  7. }

三、滚动数组内存优化

由上述的递推表达式 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) ，我们可以清晰的发现任何一个此时选区的i物品的状态都依赖且只依赖于选取i-1物品时的状态，因此我们可以给dp数组降维，改为一轮一轮刷新覆盖一维数组来做到相同的效果

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

为什么背包的遍历顺序反过来了呢，这个问题网上很少有帖子能把它真正讲明白：

我们只看dp[j]=dp[j-weight[i]]这一步，因为是这一轮大容量背包可能找上一轮小容量背包要答案，如果此时背包在从小到大遍历，你这一步大容量背包找的小容量背包不再是上一轮了，而是这一轮的小容量背包，因此我们需要从后往前遍历容量，确保你大容量背包找的小容量背包是上一轮未被修改过的

四、Leetcode实战

当然大多数此类问题会在我们刚刚讲的经典01背包基础上做一些变化，我们需要根据最基础的01背包理论将这些问题转化为我们能够熟悉的01背包，然后再解决它们

Leetcode.416 分割等和子集

方法一：

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.     //01背包问题转化思路:在0...i中选取nums中的元素，能否恰好装满容量为nums和一半的背包
  5.     //dp数组及其含义:dp[i][j]-->前i里面挑，能否挑出和为j
  6.     //递推公式：dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]]
  7.     //初始化:dp[i][0]=true dp[0][nums[0]]=true
  8.     int total=0;
  9.     for(int i=0;i<nums.size();i++){
  10.     total+=nums[i];
  11.     }
  12.     if(total%2!=0)return false;//base case:总和为奇数直接返回
  13.     int target=total/2;
  14.     //创建dp数组
  15.     vector<vector<bool>>dp(nums.size(),vector<bool>(target+1,false));
  16.     //进行dp数组的初始化
  17.     for(int i=0;i<nums.size();i++){
  18.         dp[i][0]=true;
  19.     }
  20.     if(target>=nums[0])
  21.     dp[0][nums[0]]=true;
  22.     for(int i=1;i<nums.size();i++){
  23.         for(int j=1;j<=target;j++){
  24.             if(j<nums[i])dp[i][j]=dp[i-1][j];
  25.             else dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]];
  26.         }
  27.     }
  28.     return dp[nums.size()-1][target];
  29.  
  30.     }
  31. };

滚动数组优化:

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.     int total=0;
  5.     for(int i=0;i<nums.size();i++){
  6.     total+=nums[i];
  7.     }
  8.     if(total%2!=0)return false;
  9.     int target=total/2;
  10.     vector<int>dp(target+1,0);
  11.     for(int i=0;i<nums.size();i++){
  12.         for(int j=target;j>=nums[i];j--){
  13.             dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
  14.             if(dp[target]==target)return true;
  15.         }
  16.     }
  17.     return false;
  18.  
  19.     }
  20. };

方法二：

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.     //01背包问题转化思路:在0...i中选取nums中的元素，能否恰好装满容量为nums和一半的背包
  5.     //dp数组及其含义:dp[i][j]-->前i里面挑，容量为j的背包最大价值(每件物品的价值等于其重量)
  6.     //递推公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])
  7.     //初始化:dp[0][nums[0]...target]=nums[0]
  8.     int total=0;
  9.     for(int i=0;i<nums.size();i++){
  10.     total+=nums[i];
  11.     }
  12.     if(total%2!=0)return false;//base case:总和为奇数直接返回
  13.     int target=total/2;
  14.     //创建dp数组
  15.     vector<vector<int>>dp(nums.size(),vector<int>(target+1,0));
  16.     //进行dp数组的初始化
  17.     for(int i=nums[0];i<=target;i++){
  18.         dp[0][i]=nums[0];
  19.     }
  20.     for(int i=1;i<nums.size();i++){
  21.         for(int j=1;j<=target;j++){
  22.             if(j<nums[i])dp[i][j]=dp[i-1][j];
  23.             else dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
  24.         }
  25.     }
  26.     return dp[nums.size()-1][target]==target;
  27.  
  28.     }
  29. };

 滚动数组优化:

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.     int total=0;
  5.     for(int i=0;i<nums.size();i++){
  6.     total+=nums[i];
  7.     }
  8.     if(total%2!=0)return false;
  9.     int target=total/2;
  10.     //创建dp数组
  11.     vector<bool>dp(target+1,false);
  12.     dp[0]=true;
  13.     //进行dp数组的初始化
  14.     for(int i=0;i<nums.size();i++){
  15.         for(int j=target;j>=nums[i];j--){
  16.          dp[j]=dp[j]|dp[j-nums[i]];
  17.          if(dp[target])return true;
  18.         }
  19.     }
  20.     return false;
  21.  
  22.     }
  23. };

Leetcode.1049 最后一块石头的重量II

  1. class Solution {
  2. public:
  3.     int lastStoneWeightII(vector<int>& stones) {
  4.     int total=0;
  5.     for(int val:stones){
  6.         total+=val;
  7.     }
  8.     int target=total/2;
  9.     vector<vector<int>>dp(stones.size(),vector<int>(target+1,0));
  10.     //容量为target的背包最多能装多少价值的物品，价值就正好等于重量
  11.     for(int i=stones[0];i<=target;i++){
  12.         dp[0][i]=stones[0];
  13.     }
  14.     for(int i=1;i<stones.size();i++){
  15.         for(int j=1;j<=target;j++){
  16.             if(j>=stones[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
  17.             else dp[i][j]=dp[i-1][j];
  18.         }
  19.     }
  20.     return total-2*dp[stones.size()-1][target];
  21.  
  22.     }
  23. };

滚动数组优化:

  1. class Solution {
  2. public:
  3.     int lastStoneWeightII(vector<int>& stones) {
  4.     int total=0;
  5.     for(int val:stones){
  6.         total+=val;
  7.     }
  8.     int target=total/2;
  9.     vector<int>dp(target+1,0);
  10.     for(int i=0;i<stones.size();i++){
  11.         for(int j=target;j>=stones[i];j--){
  12.             dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
  13.         }
  14.     }
  15.     return total-2*dp[target];
  16.  
  17.     }
  18. };

Leetcode.494 目标和

  1. class Solution {
  2. public:
  3.     int findTargetSumWays(vector<int>& nums, int target) {
  4.     //设加法总数为x，那么减法总数为sum-x,那么target需要等于2*x-sum,x=target+sum/2
  5.     int sum=0;
  6.     for(int val:nums){
  7.     sum+=val;
  8.     }
  9.     if(sum<abs(target))return 0;
  10.     if((sum+target)%2!=0)return 0;
  11.     target=(target+sum)/2;
  12.     vector<vector<int>>dp(nums.size(),vector<int>(target+1,0));
  13.     //背包能够装出价值为x的个数
  14.     //递推公式:dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+1)
  15.     if(nums[0]<=target)dp[0][nums[0]]=1;
  16.     if(nums[0]==0)dp[0][0]=2;
  17.     else dp[0][0]=1;
  18.     for(int i=1;i<nums.size();i++){
  19.         if(nums[i]==0)dp[i][0]=2*dp[i-1][0];
  20.         else dp[i][0]=dp[i-1][0];
  21.     }
  22.     for(int i=1;i<nums.size();i++){
  23.         for(int j=1;j<=target;j++){
  24.             if(j>=nums[i])dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
  25.             else dp[i][j]=dp[i-1][j];
  26.         }
  27.     }
  28.     return dp[nums.size()-1][target];
  29.  
  30.     }
  31. };

 滚动数组优化：

  1. class Solution {
  2. public:
  3.     int findTargetSumWays(vector<int>& nums, int target) {
  4.     int sum=0;
  5.     for(int val:nums){
  6.         sum+=val;
  7.     }
  8.     if((sum+target)%2!=0||sum<abs(target))return false;
  9.     vector<int>dp((sum+target)/2+1,0);
  10.     dp[0]=1;
  11.     for(int i=0;i<nums.size();i++){
  12.         for(int j=dp.size()-1;j>=nums[i];j--){
  13.             dp[j]+=dp[j-nums[i]];
  14.         }
  15.     }
  16.     return dp[dp.size()-1];
  17.     }
  18. };

Leetcode.474 一和零

  1. class Solution {
  2. public:
  3.     int findMaxForm(vector<string>& strs, int m, int n) {
  4.     //dp[i][j][k]--->挑选前i个字符串,所选出来有j个0和k个1的最大子集
  5.     //dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1)
  6.     //初始化:将下标为0的字符串中的0和1统计一下，dp[0][i>=zeroNum][j>=oneNum]=1
  7.     vector<vector<vector<int>>>dp(strs.size(),vector<vector<int>>(m+1,vector<int>(n+1,0)));
  8.     int zeroNum=0;
  9.     int oneNum=0;
  10.     for(char c:strs[0]){
  11.         if(c=='0')zeroNum++;
  12.         else oneNum++;
  13.     }
  14.     for(int i=zeroNum;i<=m;i++){
  15.         for(int j=oneNum;j<=n;j++){
  16.             dp[0][i][j]=1;
  17.         }
  18.     }
  19.     for(int i=1;i<strs.size();i++){
  20.         zeroNum=0;
  21.         oneNum=0;
  22.         for(char c:strs[i]){
  23.             if(c=='0')zeroNum++;
  24.             else oneNum++;
  25.         }
  26.         for(int j=0;j<=m;j++){
  27.             for(int k=0;k<=n;k++){
  28.                 if(j>=zeroNum&&k>=oneNum)
  29.                 dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
  30.                 else dp[i][j][k]=dp[i-1][j][k];
  31.             }
  32.         }
  33.     }
  34.     return dp[strs.size()-1][m][n];
  35.     }
  36. };

省去初始化的代码:外围数组扩一圈在for循环中进行初始化，注意，该方法仅仅是使代码更加简洁，实际上不会减少时间，反而会增加空间

  1. class Solution {
  2. public:
  3.     int findMaxForm(vector<string>& strs, int m, int n) {        
  4.     vector<vector<vector<int>>>dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));
  5.     
  6.     for(int i=1;i<=strs.size();i++){
  7.        int zeroNum=0;
  8.        int oneNum=0;
  9.         for(char c:strs[i-1]){
  10.             if(c=='0')zeroNum++;
  11.             else oneNum++;
  12.         }
  13.         for(int j=0;j<=m;j++){
  14.             for(int k=0;k<=n;k++){
  15.                 if(j>=zeroNum&&k>=oneNum)
  16.                 dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
  17.                 else dp[i][j][k]=dp[i-1][j][k];
  18.             }
  19.         }
  20.     }
  21.     return dp[strs.size()][m][n];
  22.     }
  23. };

滚动数组优化：

  1. class Solution {
  2. public:
  3.     int findMaxForm(vector<string>& strs, int m, int n) {
  4.         vector<vector<int>>dp(m+1,vector<int>(n+1,0));
  5.         for(string str:strs){
  6.             int zeroNum=0;
  7.             int oneNum=0;
  8.             for(char a:str){
  9.                 if(a=='0')zeroNum++;
  10.                 else oneNum++;
  11.             }
  12.             for(int i=m;i>=zeroNum;i--){
  13.                 for(int j=n;j>=oneNum;j--){
  14.                     dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
  15.                 }
  16.             }
  17.         }
  18.         return dp[m][n];
  19.     }
  20. };

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/332980
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号