代碼隨想錄算法訓練營|第四十四天|01背包问题 二维、01背包问题 一维、416. 分割等和子集。刷题心得（c++）

目录

01背包問題 - DP二維數組

01 背包問題描述

暴力解

動態規劃

確認DP數組以及下標的含意

確定遞推公式

01背包问题 一维

一维DP 数組(滾動数組)

動態規劃五部曲

定義DP数組以及其下標含意

遞推公式

初始化

遍歷順序

讀題

416. 分割等和子集

自己看到题目的第一想法

看完代码随想录之后的想法

416. 分割等和子集- 實作

思路

Code

總結

自己实现过程中遇到哪些困难

今日收获，记录一下自己的学习时长

相關資料

---

01背包問題 - DP二維數組

01 背包問題描述

背包最高可承重重量為j，有i件物品，每件物品的重量為weight[i]，並且對應的價值為value[i]，每件物品只能用一次

背包放入那些物品可以達到最高的價值

01 的含意，就是每件物品只能用一次，取(1)或不取(0)

暴力解

01背包問題可以使用暴力解來解出來，就是去窮舉每一個東西取或不取最後找出最大的價值和

可以使用回溯算法去做，但時間複雜度會是 $O(2^n)$

動態規劃

確認DP數組以及下標的含意

dp[i][j]: [0, i]物品任意取，可放進容量為j的背包的最大價值。

確定遞推公式

在描述中物品有兩種狀態，一個是不放入背包，一個是放入背包

1. 物品i 不放入背包: 代表我們要知道的是當下的i不放入背包j的最大價值是多少，那就是dp[i - 1][j]，背包容量為j，在不放入i之前最大的是i - 1，所以得出dp[i - 1][j]
2. 物品i放入背包: 代表我們要知道當下物品i放入背包之後，剩餘的背包重量可得到最大的價值是多少: dp[i - 1][j - weight[i]]，這代表的是，背包可承重的重量為j 減去目前i的重量weight[i]並且不包含當前i的重量，最後再加入value[i] 代表當前的價值加上扣除當前重量的背包所能得到的最大價值。最後整合為dp[i - 1][j - weight[i]] + value[i]

那我們是要取最大的數值，所以遞推公式會變成 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i] + value[i]);

01背包问题 一维

一维DP 数組(滾動数組)

藉由壓縮dp[i - 1] 到dp[i] 因為在二維的DP遞推方程裡是dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - weight[i] + value[i])

假設壓縮成一维數組，可以看成假設dp[j]跟dp[j - weight[i]] + value[i] 不用將上一層拷貝而是透過不斷更新dp[j] 來比較值。

其狀態就像是滾動著更新我們的dp数組值，透過維護dp[j]的遍歷順序來維護裡面的值與dp二維数組一致

動態規劃五部曲

定義DP数組以及其下標含意

dp[j]: 背包重量為j的最大價值為dp[j]

遞推公式

與二维數組一樣，dp[j]的數值可以透過當前dpj 以及dp[j - weighti 兩者做比較。

所以遞推公式可以將i去除掉變成

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

初始化

dp数組在dp[0]時，根據定義，需要將dp[0]初始化為0，並且根據遞推公式，每次都會取最大值，所以其他数值也應該初始化為dp数組中最小的值，也就是0

所以在初始化時，將dp数組全部初始化為0

遍歷順序

在二维數組中，每一層的數值都是當前位置的正上方以及左上方的數據得出

從二维壓縮成一维數組，我們需要模擬二维數組的方式

所以根據我們的遞推公式，我們不能使用正序遍歷，不然原本在二维數組中左上方的數據就會被覆蓋掉

而使用倒序可以保證每一層的數據都是由二维數組上一層正上方以及左上方得出的。

透過倒敘更新，確保了在考慮當前物品時，dp[j - weight[i]]仍然代表前一個物品的狀態，但是如果使用正序，那dp[j - weight[i]]就會被提早更新了

如下

假設我們有以下物品和背包：

物品重量: w = [2,3] 物品價值: v = [3,4] 背包最大容量: W = 5

1. 使用一維數組正序更新時：

   物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 |    進行的操作
   -----------------------------------    -----------
       -   | 0 | 0 | 0 | 0 | 0 | 0 |    初始化
       2   | 0 | 0 | 3 | 3 | 3 | 3 |    考慮物品1 (w=2, v=3)
       3   | 0 | 0 | 3 | 4 | 7 | 7 |    考慮物品2 (w=3, v=4)
   

   當我們考慮物品2時，對於背包容量4，dp[4]是基於dp[1]（已被更新的）和dp[4-w[2]=1]計算

2. 使用一維數組倒序更新時

   物品\\背包 | 0 | 1 | 2 | 3 | 4 | 5 |    進行的操作
   -----------------------------------    -----------
       -   | 0 | 0 | 0 | 0 | 0 | 0 |    初始化
       2   | 0 | 0 | 3 | 3 | 3 | 3 |    考慮物品1 (w=2, v=3)
       3   | 0 | 0 | 3 | 4 | 5 | 7 |    考慮物品2 (w=3, v=4)
   

   當我們考慮物品2和背包容量4時，dp[4]是基於dp[1]（尚未更新的）和dp[4-w[2]=1]計算的

在影片講解的部分，有個彈幕寫了以下這段，分享給你

一维数组就像走楼梯，你去二楼，就必须从一楼上，去三楼也要从一楼走；倒叙就还好比下楼，想去几楼都不用重复路过其他楼层。

並且需要先遍歷物品在遍歷背包，因為需要上一個物品的值，如果先遍歷背包，則只抓到一個物品的值。

讀題

416. 分割等和子集

自己看到题目的第一想法

看完跟01背包問題沒有辦法有很直接的連結，我大致有想到一個是dp[i][j]代表的是[0 ~ i][j ~ size()]的區間是否相等，但感覺有些地方沒有想清楚，先看題解。

看完代码随想录之后的想法

想法很巧妙如果有一個背包等於所有和的一半，剩下的元素相加也等於剩餘的一半 dp[j]: 容量為j的背包，最大價值為dp[j]，並且數組中的重量跟價值可以看成是一致的

並判斷dp[target] == target。dp数組初始化為0 ，並且背包重量設為target + 1

忘記思考到target如果不能被2整除，那就是要return false。

416. 分割等和子集- 實作

思路

1. 定義DP數組以及下標的含意

   target: 假設子序和的重量為總和的一半，那代表另一半為剩餘的一半。

   假設總和除2餘1代表不會有一個子序和等於另一個子序和

   dp[j] : 背包重量 j 的最大價值為dp[j]

   nums数組中，重量與價值就是nums[i]

2. 遞推公式

   dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

3. 根據遞推公式，確定DP數組如何初始化

   dp[0]要初始化為0，其他部分也要更新為正整數下的最小位数0

4. 確定遍歷順序

   避免覆蓋掉上一次的值，所以要使用倒敘遍歷

5. 打印dp數組 (debug);

Code

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int target = 0;
        for(int i = 0; i < nums.size(); i++) {
            target += nums[i];
        }
        if (target % 2 == 1) return false;
        target /= 2;
        vector<int> dp(target + 1, 0);
 
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if(dp[target] == target) return true;
        }
        return false;
    }
};

 

總結

自己实现过程中遇到哪些困难

困難點主要是在思考二维數組壓縮成一维數組的部分，這個部分思考比較久，並且在416分割等和子集中，也是遇到了點問題，在思考上沒有想到nums[i]是重量與價值相等，彈點通之後就比較理解了

今日收获，记录一下自己的学习时长

今天大概學了3hr，主要是在理解01背包的思維與想法。

相關資料

● 今日学习的文章链接和视频链接

算法圖解

01背包问题 二维

https://programmercarl.com/背包理论基础01背包-1.html

视频讲解：带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

01背包问题 一维

https://programmercarl.com/背包理论基础01背包-2.html

视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

416. 分割等和子集

本题是 01背包的应用类题目

https://programmercarl.com/0416.分割等和子集.html

视频讲解：动态规划之背包问题，这个包能装满吗？| LeetCode：416.分割等和子集_哔哩哔哩_bilibili