動態規劃之完全背包

引言：

完全背包?隸屬于動態規劃中的背包問題。而 01背包又是完全背包的基石，所以不懂01背包的，有必要了解一下。

什么是完全背包？

01背包問題：有一個背包承重為V，有N個物品，每個物品的價值(value)為v，重量為(weight)為w

，每個物品只能取1次，求問背包，最多能裝下多大價值的物品。

完全背包問題：有一個背包承重為V，有N個物品，每個物品的價值(value)為v，重量為(weight)為w，每個物品無限次存取，求問背包，最多能裝下多大價值的物品。

如上01背包與完全背包的區別就在于，能無限次存取。

舉例

如題：一個能稱重為4的背包，共有3件可裝物品。對應價值與重量如下圖所示，求最多能裝下多大價值的物品。

1、分析下標的含義：

dp[i][j] 表示，物品[ 0~i ] 每個物品，每個物品能取無數次，放入到容量為?j?的背包內，價值總和最大為多少？

2、遞推公式：

拿dp[1][4]舉例字，物品1，價值value(20)，重量weight(3)。

如上圖所示，有兩種情況：

不選擇物品本身：直接繼承物品0，也就dp[0][4] = 60；
選擇該物品：dp[ 1 ][ 4-weight ]+value =?dp[ 1 ][ 1 ]+20 也就是35；

然后從兩種選擇中，選取。

最后得出遞推公式：dp[i][j] = max(dp[i-1][j] , dp[i][j-weight] + value);

3、推導代碼（二維）：

下標的含義與遞推公式都得出來了，代碼不就直接出來了嗎：

#include <iostream>
#include <vector>
using namespace std;// 用于存儲最終的最大價值，不過在當前代碼中未實際使用該變量
int maxValue = 0;// 物品的重量和價值數組
// weight 數組存儲每個物品的重量，例如 weight[0] 是第一個物品的重量
vector<int> weight = {1, 3, 4, 5, 6};
// value 數組存儲每個物品的價值，例如 value[0] 是第一個物品的價值
vector<int> value = {1, 3, 4, 5, 6};int main(){// 背包的最大容量int bagweight = 6;// 定義二維動態規劃數組 dp// dp[i][j] 表示前 i 個物品放入容量為 j 的背包中所能獲得的最大價值int dp[weight.size()][bagweight + 1];// 初始化 dp 數組的第一行，即只考慮第一個物品的情況for(int i = 0; i <= bagweight; ++i){// 如果當前背包容量 i 小于第一個物品的重量if(i < weight[0]) {// 則無法放入第一個物品，最大價值為 0dp[0][i] = 0;} else {// 若能放入第一個物品，最大價值為第一個物品的價值// 這里由于是第一個物品，所以可以簡單理解為重復放入第一個物品來填滿背包dp[0][i] = dp[0][i - weight[0]] + value[0];}}// 外層循環遍歷物品，從第二個物品開始（索引為 1）// weight 數組的大小代表物品的個數for(int i = 1; i < weight.size(); ++i){// 內層循環遍歷背包的容量，從 0 到最大容量 bagweightfor(int j = 0; j <= bagweight; ++j){// 如果當前背包容量 j 小于第 i 個物品的重量if(j < weight[i]) {// 則無法放入第 i 個物品，最大價值和前 i - 1 個物品放入容量為 j 的背包的最大價值相同dp[i][j] = dp[i - 1][j];} else {// 若能放入第 i 個物品，需要在兩種情況中取最大值// 情況 1：不放入第 i 個物品，最大價值為 dp[i - 1][j]// 情況 2：放入第 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]);}}}// 返回 0 表示程序正常結束return 0;
}

4、壓縮（一維滾動數組）

得出二維數組之后，經觀察得到，每一行代碼，都是由本行，或者上一行推導出來的：

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

故：我們可以用疊加的思維，將二維數組壓縮成一維數組，因不斷地疊加，滾動之名也由此而來。

    int v[3]={15,20,30};int w[3] = {1,3,4};int dp[5];for(int i=0; i<3; ++i){for(int j=w[i]; j<5; ++j){dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}

理論到此結束

大綱：（經典算法題）

?1、零錢兌換 II--01背包，過渡，首次接觸動規數據越界問題

?2、組合總和 Ⅳ--排列問題-完全背包，深度思考遍歷背包與容量的順序問題

?3、爬樓梯--排列問題-動態規劃

?4、零錢兌換--組合問題，巧妙求最小值

?5、單詞拆分--結合哈希表

1、零錢兌換 II

給你一個整數數組?coins?表示不同面額的硬幣，另給一個整數?amount?表示總金額。

請你計算并返回可以湊成總金額的硬幣組合數。如果任何硬幣組合都無法湊出總金額，返回?0?。

假設每一種面額的硬幣有無限個。?

題目數據保證結果符合 32 位帶符號整數。

示例 1：
輸入：amount = 5, coins = [1, 2, 5]
輸出：4
解釋：有四種方式可以湊成總金額：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
輸入：amount = 3, coins = [2]
輸出：0
解釋：只用面額 2 的硬幣不能湊成總金額 3 。
示例 3：
輸入：amount = 10, coins = [10] 
輸出：1
提示：

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins?中的所有值?互不相同
0 <= amount <= 5000

class Solution {
// 本題相當于是（等和子集、粉碎石頭、目標和、一和零的降智難度）
// 這道題目，跟神經病一樣，數組非開到最大
public:int change(int amount, vector<int>& coins) {vector<unsigned long long> dp(amount+1,0);dp[0]=1;for(int i=0; i<coins.size(); ++i){for(int j=coins[i]; j<=amount; ++j){dp[j] = dp[j]+dp[j-coins[i]];}}return dp[amount];}
};

2、組合總和 Ⅳ

給你一個由?不同?整數組成的數組?nums?，和一個目標整數?target?。請你從?nums?中找出并返回總和為?target?的元素組合的個數。

題目數據保證答案符合 32 位整數范圍。

示例 1：
輸入：nums = [1,2,3], target = 4
輸出：7
解釋：
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
請注意，順序不同的序列被視作不同的組合。
示例 2：
輸入：nums = [9], target = 3
輸出：0
提示：

1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums?中的所有元素?互不相同
1 <= target <= 1000

class Solution {// 理解dp的，遍歷順序，比推導公式難多了！！挑戰思維// 總是有超出界限的數目，因為指數級增加，（2的多少次方）
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1);dp[0] = 1;for(int i=0; i<=target; ++i){for(int j=0; j<nums.size(); ++j){ // 疊加，指數爆炸性增長，2的多少次方，所以需要限制dp[i]+dp[i-nums[j]]<INT32_MAXif(i>=nums[j] && dp[i]<INT32_MAX - dp[i-nums[j]]) dp[i] = dp[i] + dp[i-nums[j]];}}return dp[target];}
};

3、爬樓梯

題目描述

假設你正在爬樓梯。需要 n 階你才能到達樓頂。?

每次你可以爬至多m (1 <= m < n)個臺階。你有多少種不同的方法可以爬到樓頂呢？?

注意：給定 n 是一個正整數。

輸入描述

輸入共一行，包含兩個正整數，分別表示n, m

輸出描述

輸出一個整數，表示爬到樓頂的方法數。

輸入示例
3 2
輸出示例
3
提示信息

數據范圍：
1 <= m < n <= 32;

當 m = 2，n = 3 時，n = 3 這表示一共有三個臺階，m = 2 代表你每次可以爬一個臺階或者兩個臺階。

此時你有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階段
1 階 + 2 階
2 階 + 1 階

#include <iostream>
#include <vector>
using namespace std;
int main(){int n,m;cin>>n>>m;vector<int> dp(n+1,0);dp[0] = 1;for(int i = 0; i<=n; ++i){for(int j=1; j<=m; ++j){if(i>=j) dp[i] = dp[i-j]+dp[i];}}cout<<dp[n];return 0;
}

4、零錢兌換

給你一個整數數組?coins?，表示不同面額的硬幣；以及一個整數?amount?，表示總金額。

計算并返回可以湊成總金額所需的?最少的硬幣個數?。如果沒有任何一種硬幣組合能組成總金額，返回?-1?。

你可以認為每種硬幣的數量是無限的。

示例?1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

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

5、單詞拆分

給你一個字符串?s?和一個字符串列表?wordDict?作為字典。如果可以利用字典中出現的一個或多個單詞拼接出?s?則返回?true。

注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。

示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重復使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false
提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s?和?wordDict[i]?僅由小寫英文字母組成
wordDict?中的所有字符串?互不相同

class Solution {// 相當于利用動態規劃，卡空檔位
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> uset(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=1; j<=i; ++j){string str = s.substr(i-j,j);if(uset.find(str)!=uset.end() && dp[i-j]) dp[i] = true;}}return dp[s.size()];}
};

知識點：

1、遍歷順序：（組合數與排列數）

coins是存放硬幣數組，amount 是要組成的金額數目。

組合數

for(int i=0; i<coins.size(); i++){ // 先遍歷物品for(int j=coins[i]; j<=amount; j++){ // 在遍歷背包dp[j] = dp[j] + dp[j-coins[i]];}    
}

核心邏輯：每次固定一個物品，然后更新所有能容納該背包容量的組合數。

舉例分析（coins = [1,5]，amount = 6）：

處理物品 1：
- 從 j=1 開始，所有 j>=1 的背包容量都會加上 dp [j-1]。
- 此時 dp 數組記錄的是僅使用物品 1 的組合數（全 1 的序列）。
處理物品 5：
- 從 j=5 開始，所有 j>=5 的背包容量會加上 dp [j-5]。
- 此時計算的是在已使用物品 1 的基礎上，添加物品 5 的組合。
- 最終得到的組合是類似 {1,1,1,1,1,1}、{1,1,1,1,5} 等，不會出現 5 在前 1 在后的情況，因為物品是按順序處理的，每個物品只能在其之后的容量中被添加。

排列數

for(int j=0; j<=amount; ++j){for(int i=0; i<coins.size(); ++i){if(j>=coins[i]) dp[j] += dp[j-coins[i]];}    
}

核心邏輯：每次固定一個數，嘗試將所有物品都放入，從而更新組合數。

舉例分析（coins = [1,5]，amount = 6）：

當 j=1 時：
- 遍歷物品 1，dp [1] += dp [0]（即 1 種方式：{1}）。
當 j=5 時：
- 遍歷物品 1，dp [5] += dp [4]（此時 dp [4] 可能已包含多個 1 的組合）。
- 遍歷物品 5，dp [5] += dp [0]（即 1 種方式：{5}）。
當 j=6 時：
- 遍歷物品 1，dp [6] += dp [5]（包含 {1,5} 和 {5,1} 嗎？）
- 遍歷物品 5，dp [6] += dp [1]（即 {5,1}）。