首页 > 代码库 > 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实现