j2ee网站开发免费教程,做淘宝客网站有什么服务器,清远医疗网站建设,电子商务网站开发技术解决方案0-1背包 N件物品#xff0c;背包最大容量为V, 第i件物品的费用为w[i],价值为v[i] 使用f[i][j]表示在容量为j#xff0c;在前i件物品中(包括i)选择物品所获得的最大价值 递推方程为f[i][j] max(f[i-1][j], f[i-1][j - w[i]] v[i]) 在是否选择第i件物品取最大值 从后往前更新…0-1背包 N件物品背包最大容量为V, 第i件物品的费用为w[i],价值为v[i] 使用f[i][j]表示在容量为j在前i件物品中(包括i)选择物品所获得的最大价值 递推方程为f[i][j] max(f[i-1][j], f[i-1][j - w[i]] v[i]) 在是否选择第i件物品取最大值 从后往前更新就可以使用一维数组简化f[j] max(f[j], f[j-w[i]] v[i])416. Partition Equal Subset Sum class Solution {
public:bool canPartition(vectorint nums) {int sum accumulate(nums.begin(), nums.end(), 0);return sum 1 ? false : subSum(nums, sum 1);}bool subSum(vectorint nums, int s){bool dp[s 1] {false};dp[0] true;for(int n : nums){for(int i s; i n; i--){dp[i] dp [i] || dp[i - n];}}return dp[s];}}; 完全背包 每种物品无限件, 递推方程为f[i][v]max(f[i-1][v-k*c[i]]k*w[i]|0k*c[i]v)322. Coin Change //超时
class Solution {
public:int coinChange(vectorint coins, int amount) {int n coins.size();if(amount 0) return 0;vectorvectorint f(n1, vectorint(amount1, amount 1));for(int i 0; i n; i){f[i][0] 0;for(int j 1; j amount; j){for(int k 0; k * coins[i] j; k){f[i1][j] min(f[i1][j], f[i][j - k * coins[i]] k);}}}return f[n][amount] amount 1 ? f[n][amount] : -1;}
};优化时间三重循环变为两重循环, 注意这两重循环可交换 class Solution {
public:int coinChange(vectorint coins, int amount) {int n coins.size();if(amount 0) return 0;vectorvectorint f(n1, vectorint(amount1, amount 1));for(int i 0; i n; i) f[i][0] 0;for(int j 1; j amount; j){for(int i 0; i n; i){if(j - coins[i] 0)f[i1][j] min(f[i][j], f[i1][j - coins[i]] 1);else f[i1][j] f[i][j];}}return f[n][amount] amount 1 ? f[n][amount] : -1;}
};优化空间二维数组变为一维数组 class Solution {
public:int coinChange(vectorint coins, int amount) {int n coins.size();if(amount 0) return 0;vectorint f(amount1, amount 1);f[0] 0;for(int j 1; j amount; j){for(int i 0; i n; i){if(j - coins[i] 0)f[j] min(f[j], f[j - coins[i]] 1);}}return f[amount] amount 1 ? f[amount] : -1;}
}; 518. Coin Change 2 做题的时候还是要写个二维的验证一下 class Solution {
public:int change(int amount, vectorint coins) {int n coins.size();vectorint dp(amount 1, 0);dp[0] 1;for(int i 0; i n; i){for(int j coins[i]; j amount; j){dp[j] dp[j - coins[i]];// dp[i1][j] dp[i][j] dp[i1][j - coins[i]]}}return dp[amount];}
};多重背包 初始化问题 理解合法状态要看清题目中说的是正好放满背包还是最多放满背包 前者对应dp[i][0] 0, dp[i][j] INF(j ! 0, 不是合法状态)后者对应dp[i][0] 0(全是合法状态) 参考 背包九讲 转载于:https://www.cnblogs.com/qbits/p/10982406.html
