2023年10月21日 - 动态规划6

52. 携带研究材料

 #include <iostream>
 #include <vector>
 ​
 using namespace std;
 ​
 int main()
 {
     int N, S;
     cin >> N >> S;
     vector<int> space(N, 0);
     vector<int> value(N, 0);
     for (int i = 0; i < N; i++)
     {
         cin >> space[i] >> value[i];
     }
     vector<int> dp(S + 1, 0); //装S重量所具有的最大价值
     
     for (int i = 0; i < N; i++)
     {
         for (int j = space[i]; j <= S; j++)
         {
             dp[j] = max(dp[j], dp[j - space[i]] + value[i]);
         }
     }
     cout << dp[S] << endl;
 }

【代码随想录】

 #include <iostream>
 #include <vector>
 using namespace std;
 ​
 // 先遍历背包，再遍历物品
 void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {
 ​
     vector<int> dp(bagWeight + 1, 0);
 ​
     for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
         for(int i = 0; i < weight.size(); i++) { // 遍历物品
             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;
         int v;
         cin >> w >> v;
         weight.push_back(w);
         value.push_back(v);
     }
     test_CompletePack(weight, value, V);
     return 0;
 }

518. 零钱兑换 II

组合数，类似目标和

 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. 组合总和 Ⅳ

【总结】

对于纯完全背包问题，也就是问装满背包的最大价值是多少或者能不能装满这个背包，两层for循环可以颠倒

如果问装满背包有多少种方法，需要区分是组合数还是排列数，如果是组合数，就先遍历物品在遍历背包，如果是排列数，就先遍历背包再遍历物品

 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++) { // 遍历物品
                 if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                     dp[i] += dp[i - nums[j]];
                 }
             }
         }
         return dp[target];
     }
 };