本文共 2049 字,大约阅读时间需要 6 分钟。
以后N行每行两个数Wi和Vi,表示物品的重量和价值
2 3
3 5
4 7
思路过程:
题目的关键是每个物品只有一个,不能拿物品的一半或者一些,面对每个物品,我们只有选择拿取或者不拿两种选择,不能选择拿取某物品的一部分,也不能装入同一物品多次。
解决的办法:声明一个大小为m[n][c]的二维数组,m[i][j]表示面对第i件物品,且背包容量为j时所能获取的最大价值,那么我们可以很容易分析得出m[i][j]的计算方法,
(1).当j<w[i]情况,这时候背包容量不足以放下第i件物品,只能选择不拿m[i][j]=m[i-1][j]。(用自己话来说,就是前一个背包装的物品继续装着,不把它拿出来)
(2).当j>=w[i]情况,这是背包容量可以放下第i件物品,我们就要考虑拿这件物品是否能获取更大的价值?
如果拿取,m[i][j]=m[i-1][j-w[j]]+v[i]。这里的m[i-1][j-w[j]]指的就是考虑了i-1件物品(上一件物品),背包容量为j-w[i]时的最大价值,也是相当于为第i件物品腾出了w[i]的空间。
如果不拿,m[i][j]=m[i-1][j],同(1)
究竟是拿还是不拿,自然是比较这两种情况哪一种价值最大,就选哪一个啦。。bingo~~~~~~
由此可以得到状态转移方程:
if(j>=w[i]) m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);else m[i][j]=m[i-1][j];
使用动态规划算法求解题目的0-1背包问题:使用二维数组m[i][j]存储背包剩余容量为j,可选物品i、i+1、...、n时,0-1背包问题的最优解。
价值数组v={3,5,7};
重量数组w={2,3,4};
背包容量为C=5时对应的m[i][j]数组。
0 | 1 | 2 | 3 | 4 | 5 |
1 | 0 | 3 | 3 | 3 | 3 |
2 | 0 | 3 | 5 | 5 | 8 |
3 | 0 | 3 | 5 | 7 | 8 |
下面一段话重要~~
*****如m[3][4],在面对第三件物品,背包重量为4时,我们可以选择不拿,那么获得价值仅为第一件物品的价值5,如果拿,就要把第二件物品拿出来,放第三件物品,价值7,那我们当然是选择拿啦(有价值大的物品,肯定拿取价值大的啦,没可能价值小的吧~~)。m[3][4]=m[2][0]+7=7;依次类推啦,得到m[3][5]就是考虑所有物品,背包容量为C时的最大价值。
代码如下:
import java.util.Scanner;public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int w[] = new int[n+1]; int v[] = new int[n+1]; for(int i=1;i<=n;i++){ w[i]=scanner.nextInt(); v[i]=scanner.nextInt(); } int p=maxPrice(w,v,n,m); System.out.println(p); } private static int maxPrice(int[] w, int[] v, int n, int m) { //寻找最大价值 //w:物品重量数组;v:物品价值数组;n:物品数量;m:背包的最大体积 //dp[n][m]代表在前n个物品中任取若干个存入体积为m的背包中,形成的物品最大价值 int[][] dp = new int[n+1][m+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(w[i]>j){ dp[i][j]=dp[i-1][j]; }else{ dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } } return dp[n][m]; }}
总结 01-背包问题 (动态规划算法)
转载地址:https://blog.csdn.net/xiaodingqq/article/details/78918919 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!