0/1背包问题总结

文章目录

• 🍇什么是0/1背包问题？
• 🍈例题
• • 🍉1.分割等和子集
  • 🍉2.目标和
  • 🍉3.最后一块石头的重量Ⅱ
  • 🍊总结

    

    博客主页：lyyyyrics

    🍇什么是0/1背包问题？

    0/1背包问题是一个经典的组合优化问题，其描述如下：

    假设有一个背包，它能够承载一定的重量。现在有一组物品，每个物品有各自的重量和价值。我们的目标是在不超过背包承载重量的前提下，选择一些物品放入背包中，使得背包中物品的总价值最大化。

    具体来说，假设有 n n n个物品，其重量分别为 w 1 , w 2 , . . . , w n w_1, w_2, ..., w_n w1​,w2​,...,wn​，对应的价值分别为 v 1 , v 2 , . . . , v n v_1, v_2, ..., v_n v1​,v2​,...,vn​。背包的承载重量为 W W W。我们需要在这 n n n个物品中选择一些放入背包中，使得这些物品的总重量不超过 W W W，且总价值最大化。

    数学公式可以表示为：

    Maximize ∑ i = 1 n v i x i subject to ∑ i = 1 n w i x i ≤ W x i ∈ { 0 , 1 } , i = 1 , 2 , . . . , n \begin{align*} \text{Maximize} \quad & \sum_{i=1}^{n} v_ix_i \\ \text{subject to} \quad & \sum_{i=1}^{n} w_ix_i \leq W \\ & x_i \in \{0, 1\}, \quad i=1,2,...,n \end{align*} Maximizesubject to​i=1∑n​vi​xi​i=1∑n​wi​xi​≤Wxi​∈{0,1},i=1,2,...,n​

    其中， x i x_i xi​表示第 i i i个物品是否放入背包中。若 x i = 1 x_i=1 xi​=1，表示放入；若 x i = 0 x_i=0 xi​=0，表示不放入。

    🍈例题

    🍉1.分割等和子集

    题目：

    

    样例输出和输入：

    

    根据描述，这道题就是让我们求一个数组是否能将其分成两块 ，然后这两块是相等的，如果能返回true，如果不能则返回false。

    算法原理：

    首先我们注意到，这道题要将数组分成两个部分，这两个部分是否相等，我们可以转化为分成一个部分，这个部分是数组总和的一半？很显然是可以的，这样转换之后其实就已经是背包问题了，这个数组中的数就是物品，数组中的数就代表每个物品的价值，然后数组中的数的总和的一半就是这个背包的容量，问题就 转化为，我们是否可以从数组中挑出一些物品，使得物品的体积恰好能把这个 背包塞满？

    状态表示：dp[i][j]表示前i个数中的所有的选法中，是否存在和为j的选法，如果存在则是true，如果不存在则就是false。

    状态转移方程：状态转移方程还是考虑i位置和j位置。

    

    如果能选的话，应该是选和不选中有一个满足就够了，所以这里应该还要取一个||,dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]

    初始化：

    首先看第一行，从1开始，从0个数中选，和为1的，这种情况是不存在的，所以应该是false，后面的从0个数中选的都是false，，我们来看第一列，从0个数中选和为0，那就是不选，所以为true，从1个数中选和为0，可以不选，也是true，所以我们只需要 初始化第一列，初始化为true。

    代码：

    class Solution {
    public:
        bool canPartition(vector& nums)
        {
            int n = nums.size();
            int sum = 0;
            //求和
            for (auto e : nums)sum += e;
            //如果和是奇数的话直接返回
            if (sum % 2 == 1)return false;
            //先定义一个aim表示和的一半
            int  aim = sum / 2;
            //创建dp表
            vector dp(n + 1, vector(aim + 1));
            //初始化dp表的第一列为true，因为如果和为零的话是有可能的。
            //如果什么都不选的话，当前和就是0
            for (int i = 0;i 
                dp[i][0] = true;
            }
            for (int i = 1;i 
                for (int j = 1;j 
                    //不选的话就是前一个状态的bool值
                    dp[i][j] = dp[i - 1][j];
                    //如果能选的话，只要有一种满足就表示满足
                    if (j = nums[i - 1])dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
            //返回和为aim的状态
            return dp[n][aim];
        }
    };
    
    public:
        int findTargetSumWays(vector
            int n = nums.size();
            int sum = 0;
            for (auto e : nums)sum += e;
            int aim = (sum + target) / 2;
            if (aim