完全背包

题目链接：

完全背包

代码：

#include<iostream>
#include<vector>
using namespace std;void test(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])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(weight,value,V);return 0;
}

LeetCode 518.零钱兑换Ⅱ

题目链接：

LeetCode 518.零钱兑换Ⅱ

代码：

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];}
};

LeetCode 337.组合总和Ⅱ

题目链接：

LeetCode 337.组合总和Ⅱ

代码：

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] && dp[i] < INT_MAX - dp[i - nums[j]]){dp[i]+=dp[i-nums[j]];}}}return dp[target];}
};