leetcode演算法之動態規劃（背包問題）

• 2021 年 2 月 13 日
• AI
• C/C++/C#

今天來盤一盤 **動態規劃（背包問題） ** 這類題目

這是最讓我頭疼的一類題目，一直不想做這類題目，這裡開始學習一下。

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

動態規劃（背包問題）

動規就是以空間換取時間。

0-1背包是背包問題的一個主要的表現形式，在01背包的基礎上發展出來的還有完全背包以及多維背包問題。

0-1背包

問題描述為： 存在一個容量為 C 的背包，和N類物品。這些物品分別有兩個屬性，重量w 和價值 v，每個物品的重量為w[i], 價值為v[i]，每種物品只有一個。在不超過背包容量的情況下能夠裝入最大的價值為多少？（這個背包可以不裝滿）。

如果採用暴力法，每個物品都有裝入與不裝入兩種情況，複雜度為2的n次冪，複雜度為指數級別的複雜度。如果使用動態規劃，時間複雜度會降低至O（N*C）。

dp[i][j] 為將前i件物品裝進容量為j的背包可以獲得的最大價值, 0<=i<=N, 0<=j<=C

dp表為(N+1)x(C+1)維的二維數組

• 狀態轉移方程

1. 不裝入第i件物品時，dp[i][j] = dp[i-1][j];
2. 裝入第i件物品，dp[i][j] = dp[i-1][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大於w[i])
狀態轉移方程：
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  

• base case

第0個物品時不存在的，價值為0。
dp[0][:] = 0;

• 基本的實現過程：

// 定義dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定義base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 執行狀態轉移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i-1][j-w[i]] + v[i]);	
	}
}
return dp[N][C];

• 優化的實現過程（dp採用一維數組）

初始dp[j]均為0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

完全背包

問題描述為： 存在一個容量為 C 的背包，和N類物品。這些物品分別有兩個屬性，重量w 和價值 v，每種物品的重量為w[i], 價值為v[i]，每種物品有無窮多個。在不超過背包容量的情況下能夠裝入最大的價值為多少？（這個背包可以不裝滿）。

dp[i][j] 為將前i件物品裝進容量為j的背包可以獲得的最大價值, 0<=i<=N, 0<=j<=C

dp表為(N+1)x（C+1）維的二維數組

完全背包與01背包的思路基本一致，只是每種物品可以有無限多個，因此每次裝入第i種物品後，還能繼續裝入i種物品。

• 狀態轉移方程

1. 不裝入第i種物品時，dp[i][j] = dp[i-1][j];
2. 裝入第i件物品，dp[i][j] = dp[i][ j-w[i] ] + v[i];  (j > w[i] 背包的容量大於w[i])
狀態轉移方程：
	dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])  

• base case

第0個物品時不存在的，價值為0。
dp[0][:] = 0;

• 基本的實現過程：

// 定義dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定義base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
// 執行狀態轉移
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <=C ; j++){
		dp[i][j] = dp[i-1][j];
		if (j >= w[i])
			dp[i][j]  = max(dp[i][j], dp[i][j-w[i]] + v[i]);	
	}
}
return dp[N][C];

• 優化的實現過程（dp採用一維數組）

初始dp[j]均為0
for (int i = 1; i < N+1; i++){
	for (int j = 0; j <= C; j++){
		if (j >= w[i])
			dp[j]  = max(dp[j], dp[j-w[i]] + v[i]);	
	}
}

多重背包

問題描述為： 存在一個容量為 C 的背包，和N類物品。這些物品分別有三個屬性，重量w ，價值 v和數量n，每種物品的重量為w[i], 價值為v[i]，每種物品分別有n[i]個。在不超過背包容量的情況下能夠裝入最大的價值為多少？（這個背包可以不裝滿）。

與前邊的01背包類似，不同之處在於第i件物品的數目為n[i]，這裡的分析思路就是針對第i種物品，分別可以裝入0，1，2，3, … ,n[i]件（同時還得滿足不能超過背包的容量）。

dp[i][j] 為將前i件物品裝進容量為j的背包可以獲得的最大價值, 0<=i<=N, 0<=j<=C

dp表為(N+1)x（C+1）維的二維數組

• 狀態轉移方程

1. 不裝入第i種物品時，dp[i][j] = dp[i-1][j];

2. 對於第i種物品， k為裝入第i種物品的件數, k <= min(n[i], j/w[i])
dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for i in range(k)}

	dp[i][j] = max(dp[i][j], dp[i][j-k* w[i]]+ k* v[i])  

• base case

第0個物品時不存在的，價值為0。
dp[0][:] = 0;

• 基本的實現過程：

// 定義dp
vector<vector<int>> dp(N+1, vector<int>(C+1, 0))

// 定義base case
for (int j = 0; j < c+1; j++)
	dp[0][j] = 0;
	
// 執行狀態轉移
for (int i = 1; i < N+1; i++){
	for (int j = C; j >=0 ; j--){
		dp[i][j] = dp[i-1][j];
		int tmp = min(n[i], j / w[i]);
		for (int k = 0; k<=tmp; k++){
			dp[i][j]  = max(dp[i][j], dp[i][j-k*w[i]] + k*v[i]);	
		}
	}
}
return dp[N][C];

• 優化的實現過程（dp採用一維數組）

初始dp[j]均為0
for (int i = 1; i < N+1; i++){
	for (int j = C; j >= 0; j--){
	
		int tmp = min(n[i], j / w[i]);
		
		for (int k = 0; k<=tmp; k++){
			dp[j]  = max(dp[j], dp[j-k*w[i]] + k*v[i]);	
		}
	}
}

• 416 分割等和子集（medium）
• 494 目標和（medium）
• 474 一和零（medium）
• 322 零錢兌換（medium）
• 518 零錢兌換 II（medium）
• 139 單詞拆分（medium）
• 377 組合總和 Ⅳ（medium）

416 分割等和子集（medium）

• 01背包問題

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 這就是一個01背包問題， 背包的容量為target， 能否恰好裝滿這個背包
        // nums數組的每個元素就是一種物品，nums[i]即為第i種物品的重量。
        vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
        dp[0][0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                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]];
                if (dp[i][target] == true)
                    return true;
            }
        }
        return false;
    }
};

• 優化後的一維數組解決方案

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if ( n < 2) return false;
        int numsSum = 0;
        for (auto num: nums) numsSum += num;
        if (numsSum %2 != 0) return false;
        int target = numsSum / 2;
        // 這就是一個01背包問題， 背包的容量為target， 能否恰好裝滿這個背包
        // nums數組的每個元素就是一種物品，nums[i]即為第i種物品的重量。
        vector<bool>dp (target+1, false);
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            for (int j = target; j>=0; j--){
                if (j >= nums[i-1])
                    dp[j] = dp[j] || dp[j-nums[i-1]];
                if (dp[target] == true)
                    return true;
            }
        }
        return false;
    }
};

494 目標和（medium）

• 01 背包問題， 求方案數目
• sum(P) – sum(N) = target
• sum(P) + sum(N) + sum(P) – sum(N) = target + sum(P) + sum(N)
• 2 * sum(P) = target + sum(nums)
• target為計算後的target，找子序列和為target的個數
• 背包容量為target，物品重量為元素的值

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int &num: nums) sum += num;
        if(S > sum || sum < -S) return 0; 
        if((S + sum) % 2 != 0) return 0; 
        int target = (S + sum) / 2;

        vector<int>dp(target + 1, 0);

        dp[0] = 1;
        for(int i = 1; i <= nums.size(); i++)
            for(int j = target; j >= nums[i-1]; j--)
                dp[j] = dp[j] + dp[j - nums[i-1]];

        return dp[target];
    }
};

474 一和零（medium）

• 01背包問題， 二維背包問題
• 背包的容量為m與n
• 每個物品的重量為0的個數與1的個數
• 每個物品的價值均為1， 求價值最大問題。
• dp[j][k] = max(dp[j][k], dp[j-nums[i][0]][k – nums[i][1])

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> nums(strs.size(), vector<int>(2, 0));
        int num0 = 0, num1 = 0;
        for(int i = 0; i<strs.size(); i++){
            nums[i][0] = count(strs[i].begin(), strs[i].end(), '0');
            nums[i][1] = count(strs[i].begin(), strs[i].end(), '1');
            num0 += nums[i][0];
            num1 += nums[i][1];
        }
        for (auto s: nums)
            cout<<s[0] << "  "<< s[1]<<endl;

        if (num0 == m && num1 == n) return nums.size();

        vector<vector<int>> dp (m+1, vector<int>(n+1, 0));
        for (int i = 0; i < nums.size(); i++){
            for (int j = m; j >= nums[i][0]; j--){
                for (int k = n; k >= nums[i][1]; k--){
                    dp[j][k] = max(dp[j][k], dp[j - nums[i][0]][k - nums[i][1]] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

322 零錢兌換（medium）

• 完全背包問題
• 背包容量為amount
• 每件物品的重量為coins[i]， 每件物品的價值為1， 求剛好裝滿背包的物品的價值最小。
• dp[j] = min(dp[j], dp[j-coins[i-1]]+1)

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < coins.size() + 1; i++){
            for (int j = coins[i-1]; j <= amount; j++){
                if(dp[j] - 1 > dp[j - coins[i-1]])
                    dp[j] = min(dp[j], 1 + dp[j - coins[i-1]]);   
            }
        }
        return dp[amount]==INT_MAX ? -1 : dp[amount];
    }
};

518 零錢兌換 II（medium）

• 完全背包問題
• 背包的容量為amount， 每個物品的重量為coins[i]，求剛好裝滿背包的方案數
• dp[j] = sum(dp[j] + dp[j-coins[i-1]])

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for (int i = 1; i< n+1; i++){
            for (int j = coins[i-1]; j<= amount; j++)
                dp[j] = dp[j] + dp[j- coins[i-1]];
        }
        return dp[amount];
    }
};

• 接下來的這兩道題，需要考慮輸出的順序，因此循環遍歷的順序與前邊幾道題不一致，外層遍歷背包，內層遍歷物品

139 單詞拆分（medium）

• 完全背包
• 物品就是單詞字典，每個物品可以有無數個， 背包就是字元串， 看能否完全裝滿背包

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++){ // 遍歷背包
            for (int j = 0; j < i; j++){  // 遍歷物品
                string word = s.substr(j, i - j); // 
                if (wordSet.find(word) != wordSet.end())
                    dp[i] = dp[i] || dp[j];
            }
        }
        return dp[s.size()];
    }
};

377 組合總和 Ⅳ（medium）

• 完全背包問題
• 物品的重量為nums[i]，背包容量為target， 剛好裝滿背包的組合數
• dp[j] = sum(dp[j], dp[j-nums[i-1]])

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i = 0; i < target+1; i++){ // 遍歷背包
            for (int j = 1; j < n+1; j++ ){ // 遍歷物品
                if ( i >= nums[j-1])
                    dp[i] = (dp[i] >= INT_MAX - dp[i-nums[j-1]]) ? INT_MAX : dp[i] + dp[i-nums[j-1]];
            }
        }
        return dp[target];
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn部落格： //blog.csdn.net/lxztju

• 知乎專欄： //www.zhihu.com/column/c_1101089619118026752

• AI研習社專欄：//www.yanxishe.com/column/109