題目：有A（2kg，6$）；B（2kg，3$）；C（6kg，5$）；D（5kg，4$）；E（4kg，6$）五種物品各一件，括號(hào)內(nèi)標(biāo)示該物品的重量和價(jià)值，假設(shè)你有一個(gè)容量為10kg的背包來裝上述物品，試求出可以裝下的最大價(jià)值。

分析：若裝了c物品后達(dá)到了最大價(jià)值

-------------------當(dāng)前最大價(jià)值 =（背包總重量-c物品重量）時(shí)的最大價(jià)值+c物品的價(jià)值----------------

每件物品的考慮方式：

? ? 1st:該物品重量是否大于背包總重量，大于則無法裝入背包；

? ? 2nd:若能裝入背包：

? ? ? ? v1=當(dāng)前最大價(jià)值 =（背包總重量-該物品重量）時(shí)的最大價(jià)值+c物品的價(jià)值

? ? ? ?v2=不裝該物品時(shí)背包最大價(jià)值

? ? ? ? 選v1和v2中較大者。

物品重量數(shù)組：w[6]={0,2,2,6,5,4} ? ? //增加數(shù)組長(zhǎng)度便與代碼編寫，

物品價(jià)值數(shù)組：v[6]={0,6,3,5,4,6} ? ?//增加數(shù)組長(zhǎng)度便與代碼編寫，

動(dòng)態(tài)規(guī)劃二維輔助數(shù)組：dp[6][11]? ?//增加數(shù)組長(zhǎng)度便與代碼編寫，并將第一行,列初始為0

---------------------dp[i][j]表示在前i個(gè)物品中用容量為j的背包可以裝入的最大價(jià)值-------------------

狀態(tài)轉(zhuǎn)移方程：

------------------------------------dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}-----------------------------------

核心代碼：

for（j=0;j<10;j++)

{?

? ? for(i=1;i<5;i++)

? ? {?

? ? ? ? if(w[i]>j) ?dp[i][j]=dp[i-1][j];

? ? ? ? ? ? else?

? ? ? ? ? ? {

? ? ? ? ? ? int v1=dp[i-i][j-w[i]]+v[i];

? ? ? ? ? ? int v2=dp[i-1][j];

? ? ? ? ? ? if(v1>v2) dp[i][j]=v1;

? ? ? ? ? ? ? ? else?

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? dp[i][j]=v2;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? }

}