首页 > 代码库 > 01背包问题JAVA实现
01背包问题JAVA实现
在刷华为机试的在线编程,碰到一个类似01背包问题的题目,综合了一些资料,写一些自己的理解
01背包问题就是在有限的称重容量下,求最大价值的问题
假设几个参数:
w[i]:第i个物品的重量;
p[i]:第i个物品的价值;
v[i][j]:表示在前i个物品中,总重量为j时的最大价值;
v[i-1][j-w[i]]:表示前i-1个物品中,加入第i个物品后的承重容量下的最大价值;
我们分析:在加入第i件物品前,我们要考虑要不要加进去,不加进去,那么就是v[i][j]=v[i-1][j];如果加进去,那么v[i][j]=v[i-1][j-w[i]]+p[i]
具体的例子例如
有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最大的价值总和?
首先要明确这张表是至底向上,从左到右生成的。
为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。
对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。
同理,c2=0,b2=3,a2=6。
那么状态转移方程就可以表示为:
v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+p[i]}
那么代码实现如下:
import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub int weight = 10; int n = 3; int[] w = {3,4,5}; int[] p = {4,5,6}; System.out.println(getMaxweight(w, p, weight, n)); } public static int getMaxweight(int[] w, int[] p, int weight, int n){ int[][] value = http://www.mamicode.com/new int[n+1][weight+1];>
01背包问题JAVA实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。