NC309 完全背包
问题一：求这个背包至多能装多大价值的物品？
-
状态表示：经验+题目要求
dp[i][j] 表示 从前i个物品中挑选，总体积不超过j，所有选法中，能选出来的最大价值。 -
状态转移方程
根据最后一步的状态：选还是不选，选的话选几个
这里有一个化简的过程
-
初始化
i为0，表示从前0个物品选，当然全为0；
j为0，表示从前i个物品选，总体积不超过0，也全为0；
-
填表顺序
从上往下填每一行
每一行从左往右
问题二：若背包恰好装满，求至多能装多大价值的物品？
-
状态表示：经验+题目要求
dp[i][j] 表示 从前i个物品中挑选，总体积正好等于j，所有选法中，能选出来的最大价值。 -
状态转移方程
根据最后一步的状态：选还是不选，同时当无法体积为j的时候，就令值为-1；
如果不选：dp[i][j] = dp[i-1][ j ]; 不用考虑等不等于-1
如果选： dp[i][j] = w[i] + dp[ i ][ j - v[i] ]; 但同时需要注意 j-v[i] 的大小，不能为负数。
同时需要注意dp[i-1][ j - v[i] ]不为-1
- 初始化
i为0，表示从前0个物品选，总体积正好等于 j ，除了0后面全为-1；
j为0，表示从前i个物品选，总体积正好为0，也全为0；
4. 填表顺序
从上到下
vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {// write code herevector<vector<int>> dp(n+1,vector<int>(v+1));for(int i = 1; i <= n; i++){for(int j = 1; j<=v; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1][0] >= 0)dp[i][j] = max(dp[i-1][j],dp[i][j - nums[i-1][0]] + nums[i-1][1] );}}vector<int> ret;ret.push_back(dp[n][v]);for(int j = 1; j<=v; j++)dp[0][j] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j<=v; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1][0] >= 0 && dp[i][j-nums[i-1][0]] != -1)dp[i][j] = max(dp[i-1][j],dp[i][j - nums[i-1][0]] + nums[i-1][1] );}}ret.push_back(dp[n][v] == -1 ? 0 : dp[n][v]);return ret;}
322. 零钱兑换
-
状态表示：经验+题目要求
dp[i][j] 表示 从前i个硬币中挑选，总体积正好等于j，所有选法中，最少的硬币个数。 -
状态转移方程
根据最后一步的状态：选还是不选。
同完美背包问题
- 初始化
j为0不用管， 当i为0时为了不影响min判断，我们设大值0x3f3f3f3f;
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<vector<int>> dp(n+1,vector<int>(amount+1));for(int j = 1; j<= amount; j++)dp[0][j] = INF;for(int i = 1; i <= n; i++){for(int j = 1; j<=amount; j++){dp[i][j] = dp[i-1][j];if(j - coins[i-1] >= 0)dp[i][j] = min(dp[i-1][j],dp[i][j - coins[i-1]] + 1 );}}return dp[n][amount] >= INF ? -1 : dp[n][amount];}
};
518. 零钱兑换 II
-
状态表示：经验+题目要求
dp[i][j] 表示 从前i个硬币中挑选，总体积正好等于j，所有选法中，一共有多少种方法。 -
状态转移方程
根据最后一步的状态：选还是不选。
- 初始化
class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<vector<int>> dp(n+1, vector<int>(amount+1));dp[0][0] = 1;for(int i = 1; i<=n; i++){for(int j = 0; j <= amount; j++){dp[i][j] += dp[i-1][j];if( j >= coins[i-1]){dp[i][j] += dp[i][j-coins[i-1]];} }}return dp[n][amount];}
};
