【动态规划】风扫枯杨，满地堆黄叶 - 9. 完全背包问题
本篇博客给大家带来的是完全背包问题之动态规划解法技巧.
🐎文章专栏: 动态规划
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .
王子,公主请阅🚀
要开心
要快乐
顺便进步
1. 完全背包
题目链接:DP42 【模板】完全背包
题目内容:
描述
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第i种物品的体积为
vi ,价值为wi 。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数
vi 和 wi，表示第i种物品的体积和价值。
1≤n,V≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出0。
解题须知:
完全背包问题与01背包问题的区别:
01背包问题中一种物品只能选一个.
完全背包问题种一种物品能选多个.
第一 先解决第一问
1. 状态表示
dp[i][j]表示从前 i 个物品中选,总体积不超过 j,所有选法中能选出的最大价值.
2. 状态转移方程
与01背包问题一样,
根据最后一个物品的情况来划分问题:
最后一个物品不选:dp[i][j] = dp[i-1][j];
选一个: dp[i][j] = dp[i-1][j-v[i]] + w[i];
选两个: dp[i][j] = dp[i-1][j-2×v[i]] + 2×w[i];
…
选k个: dp[i][j] = dp[i-1][j-k×v[i]] + k×w[i];
上述多种情况求最大值:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2×v[i]] + 2×w[i],…,dp[i-1][j-k×v[i]] + k×w[i]); ①
dp[i][j-v[i]] + w[i] = max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-2×v[i]] + 2×w[i],…,dp[i-1][j-h×v[i]] + h×w[i]); ②
先说结论: ①式中的k 一定等于②中的h.这是为什么呢?
在状态表示中,我们定义dp[i][j]表示从前 i 个物品中选,总体积不超过 j ,所有选法中能选出的最大价值.
随着所选物品越多, j 一定会趋于0, 无论是①还是②都一定是这样的, 所以k = h;
状态转移方程只能是有限个递推公式,所以需要化简上述式子,那么由①和②可得:
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
dp[i][j-v[i]]+w[i]式子需要保证 j >= v[i]
3. 初始化
多创建一行一列,处理两个细节:
Ⅰdp表与原数组的下标对应关系:
不做任何处理时是: i – i-1
但此题, 读入有效元素是从下标1开始的,
所以 i – i
Ⅱ初始化虚拟节点:
第一行,根据定义 当 i = 0时,没有物品,无论怎么选最大价值都是0.
第一列(除第一个位置)无需初始化, 因为 j >= v[i] 只有dp[0][0]满足.
4. 填表顺序
看状态转移方程,
要想得到dp[i][j] 就得知道dp[i-1][j]和dp[i][j-v[i]]+w[i];
所以从上往下填写每一行
每一行从左往右填写.
5. 返回值
根据状态表示和题目要求
打印 dp[n][V]即可.
6. 优化
第二 解决第二问
1. 状态表示
dp[i][j]表示从前 i 个物品中选,总体积等于 j,所有选法中能选出的最大价值.
2. 状态转移方程
根据最后一个物品的情况来划分问题:
最后一个物品不选:dp[i][j] = dp[i-1][j];
选一个: dp[i][j] = dp[i-1][j-v[i]] + w[i];
选两个: dp[i][j] = dp[i-1][j-2×v[i]] + 2×w[i];
…
选k个: dp[i][j] = dp[i-1][j-k×v[i]] + k×w[i];
上述多种情况求最大值:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],dp[i-1][j-2×v[i]] + 2×w[i],…,dp[i-1][j-k×v[i]] + k×w[i]); ①
dp[i][j-v[i]] + w[i] = max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-2×v[i]] + 2×w[i],…,dp[i-1][j-h×v[i]] + h×w[i]); ②
先说结论: ①式中的k 一定等于②中的h.这是为什么呢?
在状态表示中,我们定义dp[i][j]表示从前 i 个物品中选,总体积不超过 j ,所有选法中能选出的最大价值.
随着所选物品越多, j 一定会趋于0, 无论是①还是②都一定是这样的, 所以k = h;
状态转移方程只能是有限个递推公式,所以需要化简上述式子,那么由①和②可得:
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
dp[i][j-v[i]]+w[i]式子需要保证 j >= v[i]
第二问需要多考虑一个细节, 所选择的 i 物品并不一定能够保证 j-v[i] 恰好等于0, 有可能背包体积有剩余.
当背包体积有剩余时,规定dp[i][j-v[i]] = -1;
于是需要满足条件:
j - v[i] >= 0 && dp[i][j-v[i]] != -1;
3. 初始化
多创建一行一列,处理两个细节:
Ⅰdp表与原数组的下标对应关系:
不做任何处理时是: i – i-1
但此题, 读入有效元素是从下标1开始的,
所以 i – i
Ⅱ初始化虚拟节点:
第一行,根据定义 当 i = 0且j >= 1时,没有物品可选, 意味着背包体积有剩余.故dp[0][j] = -1;
第一列(除第一个位置)无需初始化, 因为 j >= v[i] 只有dp[0][0]满足.
4. 填表顺序
看状态转移方程,
要想得到dp[i][j] 就得知道dp[i-1][j]和dp[i][j-v[i]]+w[i];
所以从上往下填写每一行
每一行从左往右填写.
5. 返回值
根据状态表示和题目要求
打印 dp[n][V]即可.
6. 优化
第三 代码实现
//优化前:// Scanner in = new Scanner(System.in);// // 注意 hasNext 和 hasNextLine 的区别// int N = 1010;// int[][] dp = new int[N][N];// int[][] dp2 = new int[N][N];// int[] v = new int[N];// int[] w = new int[N];// int n = in.nextInt();// int V = in.nextInt();// for(int i = 1;i <= n;i++) {// v[i] = in.nextInt();// w[i] = in.nextInt();// }// //解决第一问// for(int i = 1;i <= n;++i) {// for(int j = 0;j <= V;++j) {//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.// dp[i][j] = dp[i-1][j];// if(j >= v[i]) {// dp[i][j] = Math.max(dp[i][j],dp[i][j-v[i]]+w[i]);// }// }// }// System.out.println(dp[n][V]);// //解决第二问// for(int i = 1;i <= V;++i) {// dp2[0][i] = -1;// }// for(int i = 1;i <= n;++i) {// for(int j = 0;j <= V;++j) {//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.// dp2[i][j] = dp2[i-1][j];// if(j >= v[i] && dp2[i][j-v[i]] != -1) {// dp2[i][j] = Math.max(dp2[i][j],dp2[i][j-v[i]]+w[i]);// }// }// }// System.out.println(dp2[n][V] == -1 ? 0 : dp2[n][V]);//优化后:Scanner in =newScanner(System.in);// 注意 hasNext 和 hasNextLine 的区别intN=1010;int[] dp =newint[N];int[] dp2 =newint[N];int[] v =newint[N];int[] w =newint[N];int n = in.nextInt();intV= in.nextInt();for(int i =1;i <= n;i++){ v[i]= in.nextInt(); w[i]= in.nextInt();}//解决第一问for(int i =1;i <= n;++i){for(int j =0;j <=V;++j){//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.if(j >= v[i]){ dp[j]=Math.max(dp[j],dp[j-v[i]]+w[i]);}}}System.out.println(dp[V]);//解决第二问for(int i =1;i <=V;++i){ dp2[i]=-1;}for(int i =1;i <= n;++i){for(int j =0;j <=V;++j){//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置. dp2[j]= dp2[j];if(j >= v[i]&& dp2[j-v[i]]!=-1){ dp2[j]=Math.max(dp2[j],dp2[j-v[i]]+w[i]);}}}System.out.println(dp2[V]==-1?0: dp2[V]);}}2. 零钱兑换
题目链接:322. 零钱兑换
题目内容:
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
第一 动态规划
1. 状态表示
dp[i][j]表示从前 i 个硬币中选,总金额等于 j,所有选法中能选出的最少硬币个数.
2. 状态转移方程
根据最后一个物品的情况来划分问题:
最后一个物品不选:dp[i][j] = dp[i-1][j];
选一个: dp[i][j] = dp[i-1][j-coins[i]] + 1;
选两个: dp[i][j] = dp[i-1][j-2×coins[i]] + 2;
…
选k个: dp[i][j] = dp[i-1][j-k×coins[i]] + k;
上述多种情况求最小值:
dp[i][j] = min(dp[i-1][j],dp[i-1][j-coins[i]]+1,dp[i-1][j-2×coins[i]] + 2,…,dp[i-1][j-k×coins[i]] + k); ①
dp[i][j-v[i]] + 1 = min(dp[i-1][j-coins[i]]+1,dp[i-1][j-2×coins[i]] + 2,…,dp[i-1][j-h×coins[i]] + h); ②
先说结论: ①式中的k 一定等于②中的h.这是为什么呢?
在状态表示中,我们定义dp[i][j]表示从前 i 个硬币中选,总金额不超过 j ,所有选法中能选出的最少硬币个数.
随着所选硬币越多, j 一定会趋于0, 无论是①还是②都一定是这样的, 所以k = h;
状态转移方程只能是有限个递推公式,所以需要化简上述式子,那么由①和②可得:
dp[i][j] = max(dp[i-1][j],dp[i][j-coins[i]]+1);
dp[i][j-coins[i]]+1式子需要保证 j >= v[i]
还需要多考虑一个细节, 所选择的 i 硬币并不一定能够保证 j-coins[i] 恰好等于0, 有可能背包有剩余.
当背包有剩余时,规定dp[i][j-硬币[i]] = 0x3f3f3f3f;
于是需要满足条件:
j - coins[i] >= 0 && dp[i][j-coins[i]] != 0x3f3f3f3f;
3. 初始化
多创建一行一列,处理两个细节:
Ⅰdp表与原数组的下标对应关系:
i – i-1
Ⅱ初始化虚拟节点:
第一行,根据定义 当 i = 0且j >= 1时,没有硬币可选, 意味着背包有剩余.故dp[0][j] = 0x3f3f3f3f;
第一列(除第一个位置)无需初始化, 因为 j >= coins[i] 只有dp[0][0]满足.
4. 填表顺序
看状态转移方程,
要想得到dp[i][j] 就得知道dp[i-1][j]和dp[i][j-coins[i]]+1;
所以从上往下填写每一行
每一行从左往右填写.
5. 返回值
根据状态表示和题目要求
return dp[coins.length][amount]即可.
6. 优化
第二 代码实现
classSolution{publicintcoinChange(int[] coins,int amount){//优化前:// int n = coins.length;// int[][] dp = new int[n+1][amount+1];// //2.初始化// for(int i = 1;i <= amount;++i) {// dp[0][i] = Integer.MAX_VALUE;// } // //3.填表// for(int i = 1;i <= n;++i) {// for(int j = 0;j <= amount;++j) {//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.// dp[i][j] = dp[i-1][j];// if(j >= coins[i-1] && dp[i][j-coins[i-1]] != Integer.MAX_VALUE) {// dp[i][j] = Math.min(dp[i][j],dp[i][j-coins[i-1]]+1);// }// }// }// return dp[n][amount] == Integer.MAX_VALUE ? -1 : dp[n][amount];//优化后:int n = coins.length;int[] dp =newint[amount+1];//2.初始化for(int i =1;i <= amount;++i){ dp[i]=0x3f3f3f3f;}//3.填表for(int i =1;i <= n;++i){for(int j =0;j <= amount;++j){//j需要从0开始,因为初始化的时候并没有考虑第一列的全部位置,只考虑了第一列的第一个位置.if(j >= coins[i-1]&& dp[j-coins[i-1]]!=0x3f3f3f3f){ dp[j]=Math.min(dp[j],dp[j-coins[i-1]]+1);}}}return dp[amount]==0x3f3f3f3f?-1: dp[amount];}}本篇博客到这里就结束啦, 感谢观看 ❤❤❤
🐎期待与你的下一次相遇😊😊😊
