代碼隨想錄算法訓練營第四十六天

KM52. 攜帶研究材料

題目鏈接：KM52. 攜帶研究材料

1. 確定dp數組以及下標的含義：j的含義是當前背包的最大容量，dp[j]背包內物品的總價值
2. 確定遞推公式：背包最大容量固定為j，每個循環嘗試在當前最大容量下，把物品往背包里試著放一下，面臨2種情況：
   1. 最大容量不夠放入當前選擇的物品，背包內最大的價值就是原來的dp[j]，
   2. 最大容量能放下當前選擇的物品，價值為dp[j-wights[i]]+values[i]，將wights[i]這么多空間價值的物品取出，在把當前物品的價值放進去的總價值，或者不進行這個交換的總價值哪個更大
3. dp數組如何初始化：背包容量為0，沒法放物品，價值就都是0，
4. 確定遍歷順序：完全背包：從小到大，表示可以把同一物品放進背包多次。01背包：從大到小，表示每個物品只能放一次。
5. 打印dp數組。

#include <iostream>
#include <vector>using namespace std;
int main(){int N;int V;cin >>N>>V ;vector<int> wights(N);vector<int> values(N);for(int i = 0;i<N;i++){cin>>wights[i]>>values[i];}vector<int>dp(V+1);for(int i = 0;i<N;i++){for(int j = wights[i];j<=V;j++)dp[j] = max(dp[j],dp[j-wights[i]]+values[i]);}cout<<dp[V];return 0;
};

---

518. 零錢兌換 II

題目鏈接：518. 零錢兌換 II

1. 確定dp數組以及下標的含義：j為背包的最大容量，dp[j]當容量為j有幾種組合方式
2. 確定遞推公式：dp[j]=dp[j]+dp[j-nums[i]]，不放當前數字組成目標值的種類+必須放當前數字組成目標值的種類（為了保證一定放這個值，就要把需要的容量騰出來）
3. dp數組如何初始化：容量為0，有一種放法，dp[0] = 1;
4. 確定遍歷順序：先遍歷物品，再遍歷背包容量，求出來的是組合種類；先遍歷背包容量再變量物品，求出來每個容量下不同物品排列的種類數。本題屬于前者。
5. 打印dp數組。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int>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-coins[i]];}}return dp[amount];}
};

---

377. 組合總和 Ⅳ

題目鏈接：377. 組合總和 Ⅳ

1. 確定dp數組以及下標的含義：j為背包的最大容量，dp[j]當容量為j有幾種組合方式
2. 確定遞推公式：dp[j]=dp[j]+dp[j-nums[i]]，不放當前數字組成目標值的種類+必須放當前數字組成目標值的種類（為了保證一定放這個值，就要把需要的容量騰出來）
3. dp數組如何初始化：容量為0，有一種放法，dp[0] = 1;
4. 確定遍歷順序：先遍歷物品，再遍歷背包容量，求出來的是組合種類；先遍歷背包容量再變量物品，求出來每個容量下不同物品排列的種類數。本題屬于后者。
5. 打印dp數組。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int j = 1; j <= target; j++) {for (int i = 0; i < nums.size(); i++) {if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) {dp[j] += dp[j - nums[i]];}}}return dp[target];}
};

---