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

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

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

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