动态规划算法0-1背包有关问题java实现

动态规划算法0-1背包问题java实现

问题描述：给定n种物品和一背包，物品i的重量是wi，其价值是pi，背包的容量是M，问如何选择装入背包中的物品总价值最大？

 

import java.util.ArrayList;
import java.util.HashMap;

/*
 * 实际就是一种分而治之的思想
 *   
每次加入新物品i的时候,将总的容量-物品i的容量即是前i-1种物品可以使用的，得出的价值+i的价值
与不加入物品i的价值看谁大
max{f(i-1,w),v(i)+f(i-1,w-wi)} w-wi为扣除i的剩余容量，在该容量情况下前i-1个物品的最大价值+i的价值与前i-1个物品在总容量不扣除i容量的情况下取更优方案
 * 
 * 
 * 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。因为背包的最终最大容量未知，
 * 所以，我们得从1到M一个一个的试,看放进去与不放进去哪个选择更优 */

public class DynamicPlan {

	public static void main(String[] args)
	{
		//第一维下标i表示物品id,第二维下标j表示各个容量值,数组实际值代表价值,c[0][..]全部赋值为0,以便第一
		int c[][]=new int[4][11];
	ArrayList<ArrayList<Integer>> al=new ArrayList<ArrayList<Integer>>();
	

	//物品1
	
	ArrayList<Integer> al1=new ArrayList<Integer>();
	al1.add(3); //物品大小
	al1.add(4);  //物品价值
	al.add(al1);
	
	
	//物品2
	
	ArrayList<Integer> al2=new ArrayList<Integer>();
	al2.add(4);
	al2.add(5);
	al.add(al2);
	
	
	

	//物品3
	ArrayList<Integer> al3=new ArrayList<Integer>();
	al3.add(5);
	al3.add(6);
	al.add(al3);
	
	for (int a=0;a<=10;a++)
		c[0][a]=0;
	
	int itemcount=al.size();
	for (int i=0;i<itemcount;i++)
	{
		int index=i+1; //物品id从1开始
		for (int j=0;j<=10;j++)
		{
			//如果当前物品的重量小于容量j,才考虑后续处理
			if (al.get(i).get(0)<=j)
			{
				//加入物品i的情况,当前容量(j)减去i的容量即是前i-1种物品可使用的容量,容量下i-1种物品的价值+当前物品i的价值
				//与不加物品i的价值对比
			int temp=Math.max(c[index-1][j-al.get(i).get(0)]+al.get(i).get(1), c[index-1][j]);	
				c[index][j]=temp;
				
					
			}
			else
			{
				c[index][j]=c[index-1][j];
			}
				
				
			
		
		}
		
	}
	
	System.out.println(c[3][10]);
	

	
	}
}

参考:

http://blog.sina.com.cn/s/blog_6dcd26b301013810.html,算法原理讲的比较细致