筆者心得
0-1背包問(wèn)題一直是筆者的心頭大患，從第一次接觸到現(xiàn)在做了三四遍了，愣是感覺(jué)有點(diǎn)不能熟練掌握羡铲，所有你大可不必因?yàn)橐淮巫龅秒y受而煩惱，大家都一樣哦儡毕。??
下面筆者力求用最簡(jiǎn)潔的語(yǔ)言與代碼來(lái)解決這個(gè)問(wèn)題也切。
解題思路
設(shè)共有l(wèi)en件物品，重量數(shù)組為weight[],價(jià)值容量為value[],背包容量為V(注意這里是大寫(xiě)的“V”)腰湾。
先寫(xiě)表達(dá)式：
dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-weight[i-1]]+value[i-1]);
關(guān)于表達(dá)式
我們用dp[i][v]來(lái)表示將前i件物品裝入容量為v(注意這里是小寫(xiě)的“v”)的背包所獲得的最大價(jià)值雷恃，那么它可以由兩個(gè)狀態(tài)轉(zhuǎn)移而來(lái)，其一是dp[i-1][v],表示沒(méi)有裝第i件物品费坊，還有則是dp[i-1][v-weight[i]]+value[i],這里與上面表達(dá)式下標(biāo)不同倒槐，只是因?yàn)槭褂昧藈eight[0]與value[0]表示第一件物品，那么weight[i-]與value[i-1]則表示第i件物品附井。
上面表達(dá)式還有一點(diǎn)則是dp[i-1][v-weight[i]]+value[i],很多同學(xué)不理解數(shù)組后半部分為什么要用v-weight[i]讨越，只用v，即將前i物品裝入容量為v的背包獲得的價(jià)值=將前i-1件物品裝入容量為v的背包可以獲得的價(jià)值+物品i的價(jià)值永毅。假設(shè)我們總共5件物品把跨，只能裝入容量為8的背包兩件，而可以裝入容量為6的背包一件沼死，這顯然是不等價(jià)的着逐。
關(guān)于循環(huán)
for(int i=1;i<=len;i++) {
for(int v=weight[i-1];v<=V;v++){...}
}
筆者一直對(duì)第二層循環(huán)很糾結(jié)，首先由于v表示容量，我們很少寫(xiě)這樣的循環(huán)耸别，這里由于容量都是整數(shù)健芭，而且我們轉(zhuǎn)移方程需要不同容量的背包，因此我們需要計(jì)算對(duì)于不同容量的背包裝入前i件物品所獲得的最大價(jià)值秀姐，當(dāng)然這里v不能從1開(kāi)始吟榴，因?yàn)槲覀兊霓D(zhuǎn)移方程需要v-weight[i],而且將前1件物品裝入容量需求比它所需要的容量更小的背包是不實(shí)際的。
附代碼
public static void main(String[] args) {
int weight[] = {3,5,1,2,2};
int value[] = {4,5,2,1,3};
int V =8;
System.out.println(Bag_01(weight, value, V));
// System.out.println(Bag_01_2(weight, value, V));
}
public static int Bag_01(int weight[],int value[],int V) {
int len = weight.length;
int res =0;
int dp[][] = new int[len+1][V+1];
for(int v=0;v<=V;v++) {
//將前0件物品裝入容量為v的背包所獲得的最大價(jià)值
dp[0][v] =0;
}
for(int i=1;i<=len;i++) {
for(int v=weight[i-1];v<=V;v++) {
dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-weight[i-1]]+value[i-1]);
}
System.out.println("\n");
}
for(int i=1;i<=len;i++) {
if(dp[i][V]>res)
res = dp[i][V];
}
return res;
}
