动态规划-背包问题

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(vector<int>& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); return sum & 1 ? false : subSum(nums, sum >> 1); } bool subSum(vector<int>& 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]|0<=k*c[i]<=v)322. Coin Change

//超时 class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); if(amount == 0) return 0; vector<vector<int>> f(n+1, vector<int>(amount+1, 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[i+1][j] = min(f[i+1][j], f[i][j - k * coins[i]] + k); } } } return f[n][amount] < amount + 1 ? f[n][amount] : -1; } };

优化时间，三重循环变为两重循环, 注意这两重循环可交换

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); if(amount == 0) return 0; vector<vector<int>> f(n+1, vector<int>(amount+1, 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[i+1][j] = min(f[i][j], f[i+1][j - coins[i]] + 1); else f[i+1][j] = f[i][j]; } } return f[n][amount] < amount + 1 ? f[n][amount] : -1; } };

优化空间，二维数组变为一维数组

class Solution { public: int coinChange(vector<int>& coins, int amount) { int n = coins.size(); if(amount == 0) return 0; vector<int> f(amount+1, 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, vector<int>& coins) { int n = coins.size(); vector<int> 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[i+1][j] = dp[i][j] + dp[i+1][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

相关资源：0-1背包问题——动态规划