动态规划算法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>>();//物品1ArrayList<Integer> al1=new ArrayList<Integer>();al1.add(3); //物品大小al1.add(4); //物品价值al.add(al1);//物品2ArrayList<Integer> al2=new ArrayList<Integer>();al2.add(4);al2.add(5);al.add(al2);//物品3ArrayList<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,算法原理讲的比较细致