0-1背包問題（一）

系列文章目錄

0-1背包問題（一）

提示：寫完文章後，目錄可以自動生成，如何生成可參考右邊的幫助文檔

---

前言

提示：以下是本篇文章正文內容，下面案例可供參考

一、0-1背包問題是什麼？

背包問題是「動態規劃」中十分經典的一類問題，背包問題本質上屬於組合優化的「NP 完全問題」。因為組合數量過多，因此無法通過窮舉法來解决問題，這就是為什麼「背包問題」會使用「動態規劃」來求解的根本原因。下面通過簡單示例來講述0-1背包問題。

二、分割等和子集（Leetcode 416中等）

1.問題描述

給你一個 只包含正整數 的 非空 數組 nums 。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

2.算法概述

2.1 0-1背包問題問題的基本思路

0-1背包問題本質上還是動態規劃問題，動態規劃的問題的本質在於尋找下一個狀態和上個狀態的變化帶來的數值變化，即狀態轉移方程，dp[i][j]和dp[i-1][j]之間的關系。
0-1背包問題其實也是同樣的問題，dp[i][j]=max(dp[i-1][j],dp[i-1][jv[i]]+wight[i]),意思就是每次遍曆到一個物品，都有兩個選擇：取或者不取，取了背包的容積就會减少，不取則保持原來的狀態。

2.2 具體問題分析

此題可以轉換為背包問題，問題建模過程：背包的容積有多大、物品的數量和價值、結果形式

1.物品的數量：nums的size
2.物品的價值：nums對應的數值
3.背包的容積：這個是一般形如背包問題的難點，此處題中並沒有明說背包最大值是多少，此時需要把問題變形：使兩個子集的元素和相等==》每個子集的和==所有元素和的1/2，因此背包的容積也顯而易見即所有元素和的1/2。
4.結果形式：首先得分析我們計算出來的結果是什麼，計算獲得的值為以此為背包容積所能獲得的最大值，問題是能否相等，因此結果的形式就可以轉換為：背包能否被裝滿，即最大值是否等於背包的容積。
本文只介紹最原始的背包問題解法，這也是最初的形式，後面幾篇都會圍繞該題做出多種變種和優化

2.4 代碼展示：

class Solution {
    
public:
    bool canPartition(vector<int>& nums) {
    
        int N=nums.size();
        int sum=0;
        for(int i=0;i<N;i++)
        {
    
            sum+=nums[i];
        }
        if(sum%2!=0) return false;
        int C=sum/2;
        vector<vector<int>>dp(N,vector<int>(C+1,0));
        // 先處理「考慮第一件物品」的情况
        for (int i = 0; i <= C; i++) {
    
            dp[0][i] = i>=nums[0] ? nums[0] : 0;
        }
        // 再處理「考慮其餘物品」的情况
        for (int i = 1; i < N; i++) {
    
            for (int j = 0; j < C + 1; j++) {
    
                // 不選該物品
                int n = dp[i - 1][j];
                // 選擇該物品，前提「剩餘容量」大於等於「物品體積」
                int y =j>nums[i]? dp[i - 1][j-nums[i]]+nums[i]:0; 
                dp[i][j] =max(n,y);
            }
        }
        return dp[N-1][C]==C;
}
};

總結

提示：這裏對文章進行總結：
今天主要講解了「什麼是背包問題」、「背包問題的本質是什麼」以及「為什麼背包問題需要用到動態規劃來求解以及背包的解决套路和變形題的難點，其中「01背包」問題是眾多背包問題中核心。