Java實(shí)現(xiàn)的0-1背包問題動態(tài)規(guī)劃算法.doc

《Java實(shí)現(xiàn)的0-1背包問題動態(tài)規(guī)劃算法.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intNum=sc.nextInt();//物品的個數(shù)（編號從0開始），不超過100intCol=sc.nextInt();//背包容量，不超過1000int[]d=newint[Col+1];//表示前i個（會不斷更新）物品裝到剩余容量為j的背包中的最大重量,當(dāng)然不包括編號為i的物品intVer=0;intWeight=0;while(sc.

2、hasNext()){for(inti=0;i<=Num;i++){//不需要用數(shù)組存儲體積和價值了，邊讀入邊處理數(shù)據(jù)即可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;}}}