代码随想录算法训练营第四十四天

sad的一天，明天开始上班，而且娃还行，媳妇儿状态不稳定，太难了也！！！

 完全背包

#include<vector>
#include<iostream>
using namespace::std;
int main(){int N;//种类int V;//空间cin >> N;cin >> V;vector<int>wi(N,0);vector<int>vi(N,0);for(int i = 0; i< N ;i++){cin >> wi[i];cin >> vi[i];}vector<int>dp(V+1,0);for(int i = 0;i < N;i++){for(int j = wi[i];j < V+1;j++){dp[j] = max(dp[j],dp[j - wi[i]]+vi[i]);}}std::cout << dp[V] << std::endl;return 0;
}

我理解的01背包和完全背包的核心代码区别：

01背包：物品在只能用一次，所以用背包空间去减当前物品的重量，然后去看是否需要用这个物品。

完全背包：用当前物品的重量去填满背包空间，然后用不同的物品去放。

 518. 零钱兑换 II  

随想录：这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇494. 目标和 (opens new window)中就讲解了，求装满背包有几种方法，公式都是：

dp[j] += dp[j - nums[i]];

class Solution {
public:int change(int amount, vector<int>& coins) {int N = coins.size();vector<int>dp(amount+1,0);dp[0] = 1;//和我昨天纠结那题一样，昨天用的是二维查表 494题for(int i = 0;i < N;i++){for(int j = coins[i];j < amount+1;j++){dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

377. 组合总和 Ⅳ  

因为存在不同顺序算不同的方法，所以for循环的内外循环需要变更，先遍历空间，再遍历物品。否则物品是有先后顺序的。

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 j = 0; j < target+1;j++){for(int i = 0;i < n;i++){if(j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]){dp[j] += dp[j - nums[i]];}}}return dp[target];}
};