Java实现的0-1背包问题动态规划算法.doc

《Java实现的0-1背包问题动态规划算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intNum=sc.nextInt();//物品的个数（编号从0开始），不超过100intCol=sc.nextInt();//背包容量，不超过1000int[]d=newint[Col+1];//表示前i个（会不断更新）物品装到剩余容量为j的背包中的最大重量,当然不包括编号为i的物品intVer=0;intWeight=0;while(sc.

2、hasNext()){for(inti=0;i<=Num;i++){//不需要用数组存储体积和价值了，边读入边处理数据即可if(i>0){Ver=sc.nextInt();Weight=sc.nextInt();}for(intj=Col;j>=0;j--){if(i>0&&j>=Ver)d[j]=(d[j]>d[j-Ver]+Weight)?d[j]:d[j-Ver]+Weight;}}System.out.println(d[Col]);break;}}}