网站聊天怎么做,邯郸制作网站的公司,一个网站怎么做app,wordpress访问报错动态规划part06 完全背包理论基础 518. 零钱兑换 II 377. 组合总和 Ⅳ
完全背包理论基础
acm可运行代码#xff08;先遍历物品再遍历背包#xff0c;一维dp#xff09;
#includeiostream
#includevector
using namespace std;int Solution(vectorint…动态规划part06 完全背包理论基础 518. 零钱兑换 II 377. 组合总和 Ⅳ
完全背包理论基础
acm可运行代码先遍历物品再遍历背包一维dp
#includeiostream
#includevector
using namespace std;int Solution(vectorint weights,vectorint values,int V){vectorint dp(V1);for(int i 0; iweights.size();i){for(int j weights[i]; jV;j){dp[j] max(dp[j],dp[j-weights[i]]values[i]);}}return dp[V];
}
int main(){int N,V;cinNV;vectorint weights(N);vectorint values(N);while(N--){int weight, value;cinweightvalue;weights.push_back(weight);values.push_back(value);}std::cout Solution(weights,values,V) std::endl;return 0;
}先遍历背包再遍历物品一维dp
#includeiostream
#includevector
using namespace std;int Solution(vectorint weights,vectorint values,int V){vectorint dp(V1);for(int j 0; j V;j){for(int i 0; iweights.size();i){if(jweights[i])dp[j] max(dp[j],dp[j-weights[i]]values[i]);}}return dp[V];
}
int main(){int N,V;cinNV;vectorint weights(N);vectorint values(N);while(N--){int weight, value;cinweightvalue;weights.push_back(weight);values.push_back(value);}std::cout Solution(weights,values,V) std::endl;return 0;
}先遍历背包再遍历物品二维dp
#includeiostream
#includevector
using namespace std;int Solution(vectorint weights,vectorint values,int V){int kinds weights.size();vectorvectorint dp(kinds,vectorint(V1,0));for(int i weights[0];iV;i){dp[0][i] dp[0][i-weights[0]]values[0];}for(int i1;iweights.size();i){for(int j 0; jV;j){if(jweights[i]){dp[i][j] max(dp[i-1][j],dp[i][j-weights[i]]values[i]);}else{dp[i][j] dp[i-1][j];}}}return dp[kinds-1][V];
}
int main(){int N,V;cinNV;vectorint weights(N);vectorint values(N);while(N--){int weight, value;cinweightvalue;weights.push_back(weight);values.push_back(value);}std::cout Solution(weights,values,V) std::endl;return 0;
}518. 零钱兑换 II
必须先遍历物品再遍历背包
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount1);dp[0] 1;for(int i 0; icoins.size();i){for(int j coins[i]; jamount;j){dp[j] dp[j-coins[i]];}}return dp[amount];}
};377. 组合总和 Ⅳ
必须先遍历背包再遍历物品
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target1);dp[0] 1;for(int j 0; j target;j){for(int i 0; inums.size();i){if(jnums[i] dp[j] INT_MAX-dp[j-nums[i]]) dp[j] dp[j-nums[i]];}}return dp[target];}
};
