完全背包
有N件物品和一個最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品都有無限個（也就是可以放入背包多次），求解將哪些物品裝入背包里物品價值總和最大。
題目鏈接：
題目頁面
求解思路：
完全背包和01背包的唯一不同就是在遍歷順序上；完全背包先遍歷背包或是物品都可以，并且需要正序遍歷
代碼：
#include <iostream>
#include <vector>
using namespace std;void solve(vector<int> weight, vector<int> value, int bagWeight){vector<int> dp(bagWeight+1, 0);for (int i = 0; i < weight.size(); i++){for (int j = 0; j <= bagWeight; j++){if (j - weight[i] >= 0)dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;
}int main(){int N, V;cin >> N >> V;vector<int> weight;vector<int> value;for (int i = 0; i < N; i++){int w, v;cin >> w >> v;weight.push_back(w);value.push_back(v);}solve(weight, value, V);return 0;
}518. 零錢兌換 II
題目鏈接：
力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺
求解思路：
本題是要求湊成總金額的物品組合個數
動規五部曲
- 確定dp數組及其下標含義：湊成總金額j的貨幣組合數為dp[j]
- 遞推公式：dp[j] += dp[j - coins[i]];（01背包題目 494.目標和）
- dp數組的初始化：dp[0] = 1
- 確定遍歷順序：本題應該先遍歷物品，再遍歷背包（求組合數）
- 舉例推導dp數組：amount = 5, coins = [1, 2, 5] ，dp狀態圖如下
代碼：
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1);dp[0] = 1;// 先物品再背包，求組合數for (int i = 0; i < coins.size(); i++){for (int j = coins[i]; j <= amount; j++){dp[j] += dp[j-coins[i]];}}return dp[amount];}
};377. 組合總和 Ⅳ
題目鏈接：
力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺
求解思路：
和上一題僅僅是遍歷順序不一樣
代碼：
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target+1, 0);dp[0] = 1;// 先遍歷背包，再遍歷物品（求排列）for (int i = 0; i <= target; i++){for (int j = 0; j < nums.size(); j++){// C++測試用例有兩個數相加超過int的數據// 需要在if里加上dp[i] < INT_MAX - dp[i - num]if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]])dp[i] += dp[i - nums[j]];}}return dp[target];}
};
)
)
