Java使用動(dòng)態(tài)規(guī)劃算法思想解決背包問(wèn)題

第Java使用動(dòng)態(tài)規(guī)劃算法思想解決背包問(wèn)題目錄動(dòng)態(tài)規(guī)劃算法動(dòng)態(tài)規(guī)劃算法的思想最優(yōu)性原理動(dòng)態(tài)規(guī)劃算法的三大特點(diǎn)動(dòng)態(tài)規(guī)劃算法中的0/1背包問(wèn)題動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)小結(jié)

動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法的思想

動(dòng)態(tài)規(guī)劃算法處理的對(duì)象是多階段復(fù)雜決策問(wèn)題，動(dòng)態(tài)規(guī)劃算法和分治算法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題(階段)，然后分別求解各個(gè)子問(wèn)題(階段)，最后將子問(wèn)題的解組合起來(lái)得到原問(wèn)題的解，但是與分治算法不同的是，子問(wèn)題往往不是相互獨(dú)立的，而是相互聯(lián)系又相互區(qū)別的

動(dòng)態(tài)規(guī)劃算法問(wèn)題求解的目標(biāo)是獲取導(dǎo)致問(wèn)題最優(yōu)解的最優(yōu)決策序列(最優(yōu)策略)。對(duì)于一個(gè)決策序列，可以用一個(gè)數(shù)值函數(shù)(目標(biāo)函數(shù))衡量這個(gè)決策的優(yōu)劣。

最優(yōu)性原理

動(dòng)態(tài)規(guī)劃算法的最優(yōu)性原理：一個(gè)最優(yōu)決策序列具有這樣的性質(zhì)，不論初始狀態(tài)和第一步?jīng)Q策如何，對(duì)前面的決策所形成的狀態(tài)而言，其余的決策必須按照前一次決策所產(chǎn)生的新?tīng)顟B(tài)構(gòu)成一個(gè)最優(yōu)決策序列。

最優(yōu)性原理體現(xiàn)為問(wèn)題的最優(yōu)子結(jié)構(gòu)特性，對(duì)于一個(gè)問(wèn)題，如果能從較小規(guī)模的子問(wèn)題的最優(yōu)解求得較大規(guī)模同類(lèi)子問(wèn)題的最優(yōu)解，最終得到給定問(wèn)題的最優(yōu)解，也就是問(wèn)題的最優(yōu)解中所包含的子問(wèn)題的最優(yōu)解，這種性質(zhì)被稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)子結(jié)構(gòu)特性使得在從較小問(wèn)題的解構(gòu)造較大問(wèn)題的解時(shí)，只需考慮子問(wèn)題的最優(yōu)解，然后以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解逐步構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解，它保證了原問(wèn)題的最優(yōu)解可以通過(guò)求解子問(wèn)題的最優(yōu)解來(lái)獲得，最優(yōu)子結(jié)構(gòu)的特性是動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的必要條件。

動(dòng)態(tài)規(guī)劃算法的三大特點(diǎn)

如果求解的問(wèn)題滿足最優(yōu)性原理，則說(shuō)明用動(dòng)態(tài)規(guī)劃算法有可能解決該問(wèn)題，在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)時(shí)，所使用的方法具有普遍性。要注意一個(gè)問(wèn)題可以有多種方式刻畫(huà)它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快(空間占用少，問(wèn)題的維度低)。遞歸定義最優(yōu)解決方案。動(dòng)態(tài)規(guī)劃的每一步?jīng)Q策都依賴(lài)于子問(wèn)題的解，動(dòng)態(tài)規(guī)劃算法求解最優(yōu)化問(wèn)題的步驟為:找出最優(yōu)解的結(jié)構(gòu)，具體來(lái)說(shuō)就是看這個(gè)問(wèn)題是否滿足最優(yōu)子結(jié)構(gòu)特性；其次遞歸定義一個(gè)最優(yōu)解的值，即構(gòu)造原問(wèn)題和子問(wèn)題之間的遞歸方程，原問(wèn)題的最優(yōu)解可以通過(guò)子問(wèn)題的最優(yōu)解獲得。以自底向上的方式計(jì)算出最優(yōu)解的值(最優(yōu)解的目標(biāo)函數(shù)的值)。對(duì)子問(wèn)題的分解是基于原問(wèn)題的分解的基礎(chǔ)之上進(jìn)行的，而且這些子問(wèn)題的分解過(guò)程是相互獨(dú)立的。在對(duì)原問(wèn)題分解的過(guò)程中，會(huì)出現(xiàn)大量的共享重疊子問(wèn)題，為了避免對(duì)大量重疊子問(wèn)題的重復(fù)計(jì)算，一般動(dòng)態(tài)規(guī)劃算法從自底向上開(kāi)始計(jì)算，對(duì)每一個(gè)問(wèn)題只解一次，并且保存求解子問(wèn)題的最優(yōu)值，當(dāng)再需要求解這個(gè)子問(wèn)題的時(shí)候，可以用常數(shù)時(shí)間查看一下結(jié)果，而不是再遞歸的去求解每一個(gè)問(wèn)題的解，因此提高了動(dòng)態(tài)規(guī)劃算法的效率。

動(dòng)態(tài)規(guī)劃算法中的0/1背包問(wèn)題

0/1背包問(wèn)題的規(guī)則是不允許該物品進(jìn)行拆分，即只有把物品放入和不放入兩個(gè)基本狀態(tài)，要使用動(dòng)態(tài)規(guī)劃算法求解決如何放物品才可以是背包中的物品的總價(jià)值達(dá)到最高。

示例

有一個(gè)載重為10的背包，現(xiàn)有4類(lèi)物品，每類(lèi)物品的重量分別為(w0,w1,w2,w3)=(2,3,4,7),它們的價(jià)值分別為(p0,p1,p2,p3)=(1,3,5,9)。試問(wèn)如何裝載能夠使背包容納物品的價(jià)值最大。

package算法設(shè)計(jì)與分析;

importjava.util.Arrays;

importjava.util.Scanner;

//m表示的是背包的容量，a表示有多少種類(lèi)的物品，數(shù)組w用與存放每類(lèi)物品的重量，數(shù)組val用于存放每類(lèi)物品的價(jià)值

publicclassmy{

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

System.out.print("請(qǐng)輸入背包的容量:");

intm=scanner.nextInt();

ScannerinScanner=newScanner(System.in);

System.out.print("請(qǐng)輸入物品的個(gè)數(shù):");

inta=inScanner.nextInt();

int[]w=newint[a+1];

System.out.print("請(qǐng)輸入物品的重量:"+"");

for(inti=1;ii++){

w[i]=inScanner.nextInt();

int[]val=newint[a+1];

System.out.print("請(qǐng)輸入物品的價(jià)值:"+"");

for(inti=1;ii++){

val[i]=inScanner.nextInt();

intn=val.length;

int[][]path=newint[n+1][m+1];

//創(chuàng)建二維數(shù)組

//v[i][j]：表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值

int[][]v=newint[n+1][m+1];

//初始化第一行和第一列

for(inti=0;iv.length;i++){//v.length:獲取二維數(shù)組的行數(shù)

v[i][0]=0;//將第一列設(shè)置為0

for(inti=0;iv[0].length;i++){//v[0].length：獲取二維數(shù)組的列數(shù)

v[0][i]=0;//將第一行設(shè)置為0

for(inti=1;iv.length;i++){//inti=1不處理第一行

for(intj=1;jv[0].length;j++){//intj=1不處理第一列

if(w[i-1]j){

v[i][j]=v[i-1][j];

}else{

if(v[i-1][j](val[i-1]+v[i-1][j-w[i-1]])){

v[i][j]=val[i-1]+v[i-1][j-w[i-1]];

//把當(dāng)前情況記錄到path

path[i][j]=1;

}else{

v[i][j]=v[i-1][j];

//輸出二維數(shù)組：

for(int[]ints:v){

System.out.println(Arrays.toString(ints));

//輸出最后我們是放入的那些商品

inti=path.length-1;//行的最大下標(biāo)

intj=path[0].length-1;//列的最大下標(biāo)

while(i0j0){//從path的最后開(kāi)始找

if(path[i][j]==1){

System.out.printf("第%d個(gè)商品放入背包\n",i-1);

j-=w[i-1];

i--;

}

輸入一個(gè)背包容量為10，里面有4類(lèi)物品，物品的重量分別為2，3，4，7，物品的價(jià)值分別為1，3，5，9

結(jié)果

動(dòng)態(tài)規(guī)劃算法的優(yōu)點(diǎn)

若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)