算法沉淀——动态规划之01背包问题（leetcode真题剖析）

算法沉淀——动态规划之01背包问题

• 01.【模板】01背包
• 02.分割等和子集
• 03.目标和
• 04.���后一块石头的重量 II

  01背包问题是一类经典的动态规划问题，通常描述为：有一个固定容量的背包，以及一组物品，每件物品都有重量和价值，目标是找到在背包容量范围内，使得背包中的物品总价值最大的组合。

  具体来说，问题的输入包括：

  1. 一个固定容量的背包（通常表示为一个整数W）。
  2. 一组物品，每个物品有两个属性：重量（通常表示为一个整数weight）和价值（通常表示为一个整数value）。
  3. 求解的目标是找到一种放置物品的方式，使得放入背包的物品的总重量不超过背包容量，并且总价值最大。

  这个问题的特点是，对于每件物品，你只能选择将其放入背包一次（0-1，因此称为“01背包”），或者不放入背包。不能将物品切割成更小的部分放入背包，要么整个物品放入背包，要么不放入。

  动态规划解法：

  1. 定义状态： 通常使用二维数组dp[i][j]表示在前i个物品中，背包容量为j时的最大总价值。

  2. 状态转移方程： 考虑第i个物品，可以选择放入背包或者不放入。如果选择放入，那么总价值为dp[i-1][j-weight[i]] + value[i]，即前i-1个物品的总价值加上当前物品的价值。如果选择不放入，那么总价值为dp[i-1][j]，即前i-1个物品的总价值。因此，状态转移方程为：

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

     其中，dp[i-1][j]表示不放入第i个物品，dp[i-1][j-weight[i]] + value[i]表示放入第i个物品。

  3. 初始条件： 当i=0时，表示前0个物品，总价值为0；当j=0时，表示背包容量为0，总价值也为0。

  4. 遍历顺序： 外层循环遍历物品，内层循环遍历背包容量。

  5. 返回结果： 最终结果存储在dp[N][W]中，其中N为物品数量，W为背包容量。

  例子：

  假设有如下物品：

  Copy code解释物品1：重量=2，价值=3物品2：重量=3，价值=4物品3：重量=4，价值=5物品4：重量=5，价值=6

  背包容量为W=8，我们要求解在这个条件下的最大总价值。

  按照上述动态规划解法，构建状态转移表如下：

  luaCopy code解释  重量/价值   0   1   2   3   4   5   6   7   8  ----------------------------------------------  物品0        0   0   0   0   0   0   0   0   0  物品1        0   0   3   3   3   3   3   3   3  物品2        0   0   3   4   4   7   7   7  10  物品3        0   0   3   4   4   7   8   8  11  物品4        0   0   3   4   4   7   8   9  11

  因此，最终结果为dp[4][8] = 11，表示在背包容量为8的情况下，最大总价值为11。这意味着最优解是选择物品2和物品4放入背包。

  01.【模板】01背包

  题目链接：https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

  你有一个背包，最多能容纳的体积是V。

  现在有n个物品，第i个物品的体积为vi,价值为wi。

  （1）求这个背包至多能装多大价值的物品？

  （2）若背包恰好装满，求至多能装多大价值的物品？

  输入描述：

  第一行两个整数n和V，表示物品个数和背包体积。

  接下来n行，每行两个数vi和wi，表示第i个物品的体积和价值。

  1≤n,V;vi,wi≤1000

  输出描述：

  输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。

  示例1

  输入：

  3 52 104 51 4

  输出：

  149

  复制

  说明：

  装第一个和第三个物品时总价值最大，但是装第二个和第三个物品可以使得背包恰好装满且总价值最大。 

  示例2

  输入：

  3 812 611 86 8

  输出：

  80

  说明：

  装第三个物品时总价值最大但是不满，装满背包无解。 要求O(nV)的时间复杂度，O(V)空间复杂度

  思路

  第一问：

  1. 状态表示：
     • dp[i][j] 表示从前 i 个物品中挑选，总体积不超过 j 的情况下，所有的选法中能挑选出的最大价值。
     • 状态转移方程：
       • 对于每个物品，我们有两种选择：
         • 不选第 i 个物品：此时 dp[i][j] = dp[i - 1][j]。
         • 选择第 i 个物品：此时需要确保总体积不超过 j - v[i]，而且该状态是合法的，即 j >= v[i] 和 dp[i - 1][j - v[i]] 存在。状态转移方程为 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])。
         • 初始化：
           • 多加一行，第一行初始化为 0，因为不选任何物品总体积为 0时，价值为 0。
           • 填表顺序：
             • 从上往下，每一行从左往右填表。
             • 返回值：
               • 返回 dp[n][V]，即最后一行最后一列的值。

  第二问：

  1. 状态表示：
     • dp[i][j] 表示从前 i 个物品中挑选，总体积正好等于 j 的情况下，所有的选法中能挑选出的最大价值。
     • 状态转移方程：
       • dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])。
       • 在使用 dp[i - 1][j - v[i]] 时，需要判断 j >= v[i] 和 dp[i - 1][j - v[i]] 是否为 -1。
       • 初始化：
         • 多加一行，第一格初始化为 0，表示正好凑齐体积为 0的背包。
         • 第一行后面的格子初始化为 -1，因为没有物品，无法满足体积大于 0的情况。
         • 填表顺序：
           • 从上往下，每一行从左往右填表。
           • 返回值：
             • 由于最后可能凑不成体积为 V 的情况，需要特判。

  代码

  #include #include #include using namespace std;const int N=1002;int n,V,v[N],w[N];int dp[N][N];int main() {    cin>>n>>V;    for(int i=1;i>v[i]>>w[i];    for(int i=1;i            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[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    cinnV;    for(int i=1;ipublic:    bool canPartition(vector        int n=nums.size(),sum=0;        for(int x:nums) sum+=x;        if(sum%2) return false;        int aim=sum/2;        vector                dp[i][j]=dp[i-1][j];                if(j=nums[i-1]) dp[i][j]=dp[i][j]||dp[i-1][j-nums[i-1]];            }        return dp[n][aim];    }};public:    bool canPartition(vector        int n=nums.size(),sum=0;        for(int x:nums) sum+=x;        if(sum%2) return false;        int aim=sum/2;        vectorpublic:    int findTargetSumWays(vector        int sum=0;        for(auto x:nums) sum+=x;        int aim=(sum+target)/2;        if(aim                dp[i][j] = dp[i - 1][j];                if(j = nums[i - 1]) dp[i][j] += dp[i - 1][j - nums[i - 1]];            }        return dp[n][aim];    }};public:    int lastStoneWeightII(vector        int sum=0;        for(int x:stones) sum+=x;        int n=stones.size(),m=sum/2;        vector                dp[i][j]=dp[i-1][j];                if(j=stones[i-1])                     dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);            }        return sum-2*dp[n][m];    }};