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

4/4動(dòng)態(tài)規(guī)劃算法每天一道算法題(四)（動(dòng)態(tài)規(guī)劃算法）01背包問(wèn)題Java實(shí)現(xiàn)

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

動(dòng)態(tài)規(guī)劃在wiki上的定義：

dynamicprogrammingisamethodforsolvingacomplexproblembybreakingitdownintoacollectionofsimplersubproblems,solvingeachofthosesubproblemsjustonce,andstoringtheirsolutions-ideally,usingamemory-baseddatastructure.Thenexttimethesamesubproblemoccurs,insteadofrecomputingitssolution,onesimplylooksupthepreviouslycomputedsolution。

昨天接觸到了動(dòng)態(tài)規(guī)劃的概念，研究了昨天一晚上以及今天一上午，總算對(duì)這個(gè)問(wèn)題有些收獲。

動(dòng)態(tài)規(guī)劃背后的基本思想非常簡(jiǎn)單。大致上，若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。

從空集合開始，每增加一個(gè)元素就求它的最優(yōu)解，直到所有元素加進(jìn)來(lái)，就得到了總的最優(yōu)解。

01背包問(wèn)題

01背包問(wèn)題即的01即每件物品最多放1件，否則不放入。

讓我真正了解動(dòng)態(tài)規(guī)劃概念的是mu399的博客

問(wèn)題：有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是

2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

重新定義問(wèn)題：

有承重分別為1-10的背包10個(gè)

編號(hào)分別為a,b,c,d,e的物品各一個(gè)

3.從e物品開始依次放入1-10個(gè)背包，分別得到最大的價(jià)值總和

4.把d物品放入依次放入存在e物品的1-10個(gè)背包，如果價(jià)值更高，替換掉e（）

5.c,b,a同理。。。

1.01背包的狀態(tài)轉(zhuǎn)換方程f[i,j]=Max{f[i-1,j-Wi]+Pi(j=Wi),f[i-1,j]}

f[i,j]：在前i件物品中選擇若干件放在承重為j的背包中，可以取得的最大價(jià)值。

Pi表示第i件物品的價(jià)值。

決策：為了背包中物品總價(jià)值最大化，第i件物品應(yīng)該放入背包中嗎？

2.以a8（行為a，列為的8的單元格）舉例

f[i,j]=a8=15

f[i-1,j]=b8=9

f[i-1,j-Wi]表示我有一個(gè)承重為6的背包（等于當(dāng)前背包承重減去物品a的重量），當(dāng)只有物品b,c,d,e四件可選時(shí)，這個(gè)背包能裝入的最大價(jià)值

f[i-1,j-Wi]+Pi=b(8-2)+6=b6+6=15背包的java代碼實(shí)現(xiàn)

publicclassgetPgAnswer{

publicvoidtestPackage(){

Package[]pg={newPackage("e",4,6),

newPackage("d",5,4),

newPackage("c",6,5),

newPackage("b",2,3),

newPackage("a",2,6)

--第一個(gè)參數(shù)表示從pg[0]開始依次放入的物品，--第二個(gè)參數(shù)代表背包的承重,放棄第0列數(shù)組

int[][]state=newint[pg.length][11];

intnewValue=0;

*01背包的狀態(tài)轉(zhuǎn)換方程

*f[i,j]=Max{

*f[i-1,j-Wi]+Pi(j=Wi),

*f[i-1,j]}

for(inti=0;ipg.length;i++){

--背包的承重量

for(intj=1;jstate[i].length;j++){

if(i==0){

if(pg[i].getWeight()=j){

state[i][j]=pg[i].getValue();

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

if(jpg[i].getWeight()){

continue;

newValue=state[i-1][j-pg[i].getWeight()]

+pg[i].getValue();

-*if(newValue=state[i-1][j]){

state[i][j]=newValue;

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

state[i][j]=Math.max(newValue,state[i-1][j]);

for(inti=0;istate.length;i++){

System.out.println(Arrays.toString(state[state.length-1-i]));

classPackage{

privateStringname;

privateintweight;

privateintvalue;

publicPackage(Stringname,intweight,intvalue){

http://./doc/9c0c87a60e22590102020740be1e650e52eacf20.html=name;

this.weight=weight;

this.value=value;

publicStringgetName(){

returnname;

publicintgetWeight(){

returnweight;

publicintgetValue(){

returnvalue;

背包的Python實(shí)現(xiàn)

問(wèn)題：有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，

現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？

思路：dynamicprogramming

即把整個(gè)問(wèn)題分解成一系列子問(wèn)題，所有子問(wèn)題只計(jì)算一次并存起來(lái)，下一次相同問(wèn)題出現(xiàn)，直接從數(shù)據(jù)結(jié)構(gòu)中取出結(jié)果，而不是再次計(jì)算K(i,j)=max(K(i-1,j),K(i-1,j-Wi)+Pi)

其中j=Wi

f[i,j]：在前i件物品中選擇若干件放在承重為j的背包中，可以取得的最大價(jià)值。

Pi表示第i件物品的價(jià)值。

決策：為了背包中物品總價(jià)值最大化，第i件物品應(yīng)該放入背包中嗎defpackage(n,c,weight,values):

構(gòu)建背包問(wèn)題二維表

:paramn:物品數(shù)量

:paramc:背包重量容積

:paramweight:物品重量列表

:paramvalues:物品價(jià)值列表

:return:

#初始化二維列表

res=[[-1forjinrange(c+1)]foriinrange(n+1)]

res[0]=[0foriinrange(1,c+1)]

#完善背包

foriinrange(1,n+1):

forjinrange(1,c+1):

res[1][j]=values[1]ifj=weights[1]else0

res[i][j]=res[i-1][j]

ifweights[i]jandres[i-1][j-weights[i]]+values[i]res[i][j]:

res[i][j]=res[i-1][j-weights[i]]+values[i]

#@Note：如果沒(méi)有上面的res[0]=[0foriinrange(1,c+1)]需要增加下面的判定

#elifweights[i]==jandvalues[i]res[i][j]:

#res[i][j]=values[i]

returnres

if__name__=='__main__':

#物品數(shù)量

#背包重量容積

#物品重量列表weights[0]無(wú)效和blog有區(qū)別博客是倒著放入商品

weights=[-1,2,2,6,5,4]

#物品價(jià)值列表values[0]無(wú)效

values=[-1,6,3,5,4,6]

res=package(n,c,weights,values)

如果枚舉的和總量大于等于選擇物品，則需要判斷是否選擇當(dāng)前物品*-

d[i][j]=min{d[i+1][j],d[i][j-1]}+1;(每次狀態(tài)轉(zhuǎn)移，區(qū)間長(zhǎng)度增加1)

描述階段的變量稱為階段變量k。階段的劃分，一般是根據(jù)時(shí)間和空間的自然特征來(lái)進(jìn)行的，但要便于問(wèn)題轉(zhuǎn)化為多階段決策。

最后一個(gè)元素相同：求X[1…m-1]和Y[1…n-1]兩個(gè)子序列的最長(zhǎng)公共子序列。

voidTrace(inti,intcapacity)

從表中可以看出一些規(guī)律，除了第一行以外，每個(gè)格