摘自Tianyi Cui童鞋的《背包問(wèn)題九講》，稍作修改，方便理解。
已知:有一個(gè)容量為V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
限制:每種物品只有一件，可以選擇放或者不放
問(wèn)題:在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值或收益
相似問(wèn)題:在恰好裝滿背包的情況下，最多能獲得多少價(jià)值或收益
這里，我們先討論在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值或收益。
基本思路
01背包的特點(diǎn):每種物品只有一件，可以選擇放或者不放
子問(wèn)題定義狀態(tài)
f[i][v] : 前i件物品放到一個(gè)容量為v的背包中可以獲得最大價(jià)值
狀態(tài)轉(zhuǎn)移方程
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] cost[i])
分析
考慮我們的子問(wèn)題，將前i件物品放到容量為v的背包中，若我們只考慮第i件物品時(shí)，它有兩種選擇，放或者不放。
1) 如果第i件物品不放入背包中，那么問(wèn)題就轉(zhuǎn)換為：將前i - 1件物品放到容量為v的背包中，帶來(lái)的收益f[i - 1][v]
2) 如果第i件物品能放入背包中，那么問(wèn)題就轉(zhuǎn)換為：將前i - 1件物品放到容量為v - weight[i]的背包中，帶來(lái)的收益f[i - 1][v - weight[i]] cost[i]
代碼
#include <iostream>
using namespace std;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[N 1][V 1] = {{0}};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[i][j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = 0;j <= V;j ) //枚舉背包容量
{
f[i][j] = f[i - 1][j];
if (j >= weight[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] value[i]);
}
}
}
return f[N][V];
}
int main()
{
cout<<Knapsack()<<endl;
system('pause');
return 1;
}效率分析：
此算法的時(shí)間復(fù)雜度為O(N*V)，空間復(fù)雜度也為O(N*V)。其中，N 表示物品個(gè)數(shù)，V 表示背包容量這里，時(shí)間復(fù)雜度不可以在優(yōu)化了，但是空間復(fù)雜度可以繼續(xù)優(yōu)化到O(V)
優(yōu)化空間復(fù)雜度
上述的方法，我們使用二維數(shù)組 f[i][v] 保存中間狀態(tài)，這里我們可以使用一維數(shù)組f[v]保存中間狀態(tài)就能得到結(jié)果
分析
我們現(xiàn)在使用f[v]保存中間狀態(tài)，我們想要達(dá)到的效果是，第i次循環(huán)后，f[v]中存儲(chǔ)的是前i個(gè)物體放到容量v時(shí)的最大價(jià)值
在回顧下之前講過(guò)的狀態(tài)轉(zhuǎn)移方程：
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] cost[i])
我們可以看到，要想得到 f[i][v]，我們需要知道 f[i - 1][v] 和 f[i - 1][v - weight[i]]，由于我們使用二維數(shù)組保存中間狀態(tài)，所以可以直接取出這兩個(gè)狀態(tài)。
當(dāng)我們使用一維數(shù)組存儲(chǔ)狀態(tài)時(shí)，f[v]表示，在執(zhí)行i次循環(huán)后(此時(shí)已經(jīng)處理i個(gè)物品)，前i個(gè)物體放到容量v時(shí)的最大價(jià)值，即之前的f[i][v]。與二維相比較，它把第一維隱去了，但是二者表達(dá)的含義還是相同的，只不過(guò)針對(duì)不同的i，f[v]一直在重復(fù)使用，所以，也會(huì)出現(xiàn)第i次循環(huán)可能會(huì)覆蓋第i - 1次循環(huán)的結(jié)果。
為了求f[v],我們需要知道，前i - 1個(gè)物品放到容量v的背包中帶來(lái)的收益，即之前的f[i - 1][v] 和 前i - 1件物品放到容量為v - weight[i]的背包中帶來(lái)的收益，即之前的f[i - 1][v - weight[i]] cost[i]。
難點(diǎn)：由于我們只使用一維數(shù)組存儲(chǔ)，則在求這兩個(gè)子問(wèn)題時(shí)就沒(méi)有直接取出那么方便了，因?yàn)?，第i次循環(huán)可能會(huì)覆蓋第i - 1次循環(huán)的結(jié)果。
現(xiàn)在我們來(lái)求這兩個(gè)值
1）前i - 1個(gè)物品放到容量v的背包中帶來(lái)的收益，即之前的f[i - 1][v] ：
由于，在執(zhí)行在i次循環(huán)時(shí)，f[v]存儲(chǔ)的是前i個(gè)物體放到容量v時(shí)的最大價(jià)值，在求前i個(gè)物體放到容量v時(shí)的最大價(jià)值(即之前的f[i][v])時(shí)，我們是正在執(zhí)行第 i 次循環(huán)，f[ v ]的值還是在第 i - 1 次循環(huán)時(shí)存下的值，在此時(shí)取出的 f[ v ]就是前i - 1個(gè)物體放到容量v時(shí)的最大價(jià)值，即f[i - 1][v]。
2）前i - 1件物品放到容量為v - weight[i]的背包中帶來(lái)的收益，即之前的f[i - 1][v - weight[i]] cost[i]
由于，在執(zhí)行第i次循環(huán)前，f[0 ~ V]中保存的是第i - 1次循環(huán)的結(jié)果，即是前i - 1個(gè)物體分別放到容量0 ~ V時(shí)的最大價(jià)值，即f[i - 1][0 ~ V]。
則，在執(zhí)行第i次循環(huán)前，f 數(shù)組中v - weight[i]的位置存儲(chǔ)就是我們要找的 前i - 1件物品放到容量為v - weight[i]的背包中帶來(lái)的收益 (即之前的f[i - 1][v - weight[i]])，這里假設(shè)物品是從數(shù)組下標(biāo)1開始存儲(chǔ)的。
偽代碼
for i=1..N //枚舉物品
for v=V..0 //枚舉容量，從大到小
f[v]=max{f[v],f[v-weight[i]] cost[i]};由上面?zhèn)未a可知，在執(zhí)行第 i 次循環(huán)時(shí)，需要把背包容量由V..0都要遍歷一遍，檢測(cè)第 i 件物品是否能放。
逆序枚舉容量的原因：
注意一點(diǎn)，我們是由第 i - 1 次循環(huán)的兩個(gè)狀態(tài)推出 第 i 個(gè)狀態(tài)的，而且 v > v - weight[i]，則對(duì)于第i次循環(huán)，背包容量只有當(dāng)V..0循環(huán)時(shí)，才會(huì)先處理背包容量為v的狀況，后處理背包容量為 v-weight[i] 的情況。
具體來(lái)說(shuō)，由于，在執(zhí)行v時(shí)，還沒(méi)執(zhí)行到v - weight[i]的，因此，f[v - weight[i]]保存的還是第i - 1次循環(huán)的結(jié)果。即在執(zhí)行第i次循環(huán) 且 背包容量為v時(shí)，此時(shí)的f[v]存儲(chǔ)的是 f[i - 1][v] ，此時(shí)f[v-weight[i]]存儲(chǔ)的是f[i - 1][v-weight[i]]。
相反，如果在執(zhí)行第 i 次循環(huán)時(shí)，背包容量按照0..V的順序遍歷一遍，來(lái)檢測(cè)第 i 件物品是否能放。此時(shí)在執(zhí)行第i次循環(huán) 且 背包容量為v時(shí)，此時(shí)的f[v]存儲(chǔ)的是 f[i - 1][v] ，但是，此時(shí)f[v-weight[i]]存儲(chǔ)的是f[i][v-weight[i]]。
因?yàn)?，v > v - weight[i]，第i次循環(huán)中，執(zhí)行背包容量為v時(shí)，容量為v - weight[i]的背包已經(jīng)計(jì)算過(guò)，即f[v - weight[i]]中存儲(chǔ)的是f[i][v - weight[i]]。即，對(duì)于01背包，按照增序枚舉背包容量是不對(duì)的。
代碼
#include <iostream>
using namespace std;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[V 1] = {0};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[j] = max{f[j],f[j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = V;j >= weight[i];j--) //枚舉背包容量,防越界，j下限為 weight[i]
{
f[j] = Max(f[j],f[j - weight[i]] value[i]);
}
}
return f[V];
}
int main()
{
cout<<Knapsack()<<endl;
system('pause');
return 1;
}但是，增序枚舉背包容量會(huì)達(dá)到什么效果：它會(huì)重復(fù)的裝入某個(gè)物品，而且盡可能多的，使價(jià)值最大，當(dāng)然不會(huì)不超過(guò)背包容量
而逆序枚舉背包容量：背包中的物品至多裝一次，使價(jià)值最大，當(dāng)然不會(huì)不超過(guò)背包容量
我們首先舉例說(shuō)明：
逆序枚舉物品
當(dāng)i = 2，我們要求 f [5]：表示檢測(cè)物品2放入容量為5的背包的最大收益
上圖表示，當(dāng)i = 2，求f[5]時(shí)f數(shù)組的狀況，
橙色為數(shù)組現(xiàn)在存儲(chǔ)的值，這些值是i = 1時(shí)(上一次循環(huán))存入數(shù)組 f 的。相當(dāng)于f[i - 1][v]
而黃色使我們要求的值，在求f[5]之前，f[5]= 5，即f[i - 1][5] = 5
現(xiàn)在要求 i = 2 時(shí)的f[5] = f[5 - 2] 10 = 5 10 = 15 > f[i - 1][5] = 5
故，f[5] = 15；
注意一點(diǎn)，在求f[v]時(shí)，它引用的 f[v - weight[i]] 和 f[v]都是上一次循環(huán)的結(jié)果
順序枚舉物品
當(dāng)i = 2，我們要求 f [5]：表示檢測(cè)物品2放入容量為5的背包的最大收益
上圖表示，當(dāng)i = 2，求f[5]時(shí)f數(shù)組的狀況，
橙色為數(shù)組現(xiàn)在存儲(chǔ)的值，這些值是i = 2時(shí)(本次循環(huán))存入數(shù)組 f 的。相當(dāng)于f[i][v]
這是由于，我們是增序遍歷數(shù)組f的，在求f[v]時(shí)，v之前的值(0 ~ v - 1)都已經(jīng)在第i次循環(huán)中求出。
而黃色使我們要求的值，在求f[5]之前，f[5]= 5，即f[i - 1][5] = 5
現(xiàn)在要求 i = 2 時(shí)的f[5] = f[5 - 2] 10 =10 10 = 20 > f[i - 1][5] = 5
故，f[5] = 20；
其中引用的f[3]是相當(dāng)于f[i][3] 而不是正常的f[i - 1][3]
注意一點(diǎn)，在求f[v]時(shí)，它引用的 f[v - weight[i]]是本次循環(huán)的結(jié)果 而f[v]是上一次循環(huán)的結(jié)果
換個(gè)角度說(shuō)，
在檢測(cè) 背包容量為5時(shí)，看物品2是否加入
由狀態(tài)轉(zhuǎn)移方程可知，我們f[5]需要引用自己本身和f[3]
由于背包容量為3時(shí)，可以裝入物品2，且收益比之前的大，所以放入背包了。
在檢測(cè)f[5]時(shí)，肯定要加上物品2的收益，而f[5]在引用f[3]時(shí)，f[3]時(shí)已經(jīng)加過(guò)一次物品2，
因此，在枚舉背包容量時(shí)，物品2會(huì)加入多次。
進(jìn)一步說(shuō)：
我們觀察一維狀態(tài)轉(zhuǎn)移方程：
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] cost[i])
首先我們明確三個(gè)問(wèn)題
1) v - weight[i] < v
2) 狀態(tài)f[i][v] 是由 f[i - 1][v] 和 f[i - 1][v - weight[i]] 兩個(gè)狀態(tài)決定
3) 對(duì)于物品i，我們?cè)诿杜e背包容量時(shí)，只要背包容量能裝下物品i 且 收益比原來(lái)的大，就會(huì)成功放入物品i。
具體來(lái)說(shuō)，枚舉背包容量時(shí)，是以遞增的順序的話，由于 v - weight[i] < v,則會(huì)先計(jì)算 v - weight[i]。在背包容量為v - weight[i]時(shí)，一旦裝入了物品i，由于求f[v]需要使用f[i - 1][v - weight[i]]，而若求f[v]時(shí)也可以裝入物品i的話，那么在背包容量為v時(shí)，容量為v的背包就裝入可兩次物品。又若v - weight[i]是由之前的狀態(tài)推出，它們也成功裝入物品i的話，那么容量為v的背包就裝入了多次物品i了。
注意，此時(shí)，在計(jì)算f[v]時(shí)，已經(jīng)把物品i能裝入的全裝入容量為v的背包了，此時(shí)裝入物品i的次數(shù)為最大啊
其實(shí)，順序枚舉容量是完全背包問(wèn)題最簡(jiǎn)捷的解決方案。
初始化的細(xì)節(jié)問(wèn)題
求最優(yōu)解的背包問(wèn)題時(shí)，有兩種問(wèn)法：
1)在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
2)在恰好裝滿背包的情況下，最多能獲得多少價(jià)值
主要的區(qū)別為是否要求恰好裝滿背包。但這兩種問(wèn)法的實(shí)現(xiàn)方法是在初始化的時(shí)候有所不同。
1)恰好裝滿背包的情況：使用二維數(shù)組f[i][v]存儲(chǔ)中間狀態(tài)，其中第一維表示物品，第二維表示背包容量
初始化時(shí)，除了f[i][0] = 0（第一列）外，其他全為負(fù)無(wú)窮。
原因：初始化 f 數(shù)組就是表示：在沒(méi)有任何物品可以放入背包時(shí)的合法狀態(tài)。對(duì)于恰好裝滿背包，只有背包容量為 0（第一列），可以什么物品都不裝就能裝滿，這種情況是合法情況，此時(shí)價(jià)值為0。其他f[0][v]（第一列）是都不能裝滿的，此時(shí)有容量沒(méi)物品。而其他位置（除去第一行和第一列的位置），我們?yōu)榱嗽谟?jì)算中比較最大值，也要初始化為負(fù)無(wú)窮。我們從程序的角度上看，我們只允許裝入背包物品的序列的起始位置是從第一列開始，這些起始位置都是合法位置，且能恰好裝滿的情況收益均為正值，到f[N][V]終止。
注意，我們雖然是求恰好裝滿，還是需要枚舉所有可以裝入背包的物品，只要能裝入，還需裝入，收益有增加。只不過(guò)，由于恰好裝滿的物品的序列肯定是從第一列某行開始的，且之后的收益肯定是正值。對(duì)于非恰好裝滿的物品序列，其實(shí)位置肯定是從第一行某位置開始的，由于此時(shí)被初始化為負(fù)無(wú)窮，在和那些恰好裝滿物品序列帶來(lái)的價(jià)值時(shí)，肯定是小的。所以，我們最后能獲得最大值。
代碼：
#include <iostream>
using namespace std;
const int MinNum = 0x80000000;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[N 1][V 1] = {{0}};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在恰好裝滿背包的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[i][j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
for (int i = 0;i <= N;i ) //枚舉物品
{
for (int j = 0;j <= V;j ) //枚舉背包容量
{
f[i][j] = MinNum;
}
}
for (int i = 0;i <= N;i )
{
f[i][0] = 0;//背包容量為0時(shí)為合法狀態(tài)
}
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = 1;j <= V;j ) //枚舉背包容量
{
f[i][j] = f[i - 1][j];
if (j >= weight[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] value[i]);
}
}
}
return f[N][V];
}
int main()
{
cout<<Knapsack()<<endl;//輸出25
system('pause');
return 1;
}使用一維數(shù)組f[v]存儲(chǔ)中間狀態(tài)，維表示背包容量
初始化時(shí)，除了f[0] = 0，其他全為負(fù)無(wú)窮。
原因：只有容量為0 的背包可以什么物品都不裝就能裝滿，此時(shí)價(jià)值為0。其它容量的背包均沒(méi)有合法的解，屬于未定義的狀態(tài)，應(yīng)該被賦值為負(fù)無(wú)窮了
代碼
#include <iostream>
using namespace std;
const int MinNum = 0x80000000;//int最小的數(shù)
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[V 1] = {0};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在恰好裝滿背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[j] = max{f[j],f[j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
for (int i = 0;i <= V;i )
{
f[i] = MinNum;
}
f[0] = 0;//只有背包容量為0時(shí)才是合法狀態(tài)，由合法狀態(tài)組成的結(jié)果才是合法的
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = V;j >= weight[i];j--) //枚舉背包容量,防越界，j下限為 weight[i]
{
f[j] = Max(f[j],f[j - weight[i]] value[i]);
}
}
return f[V];
}
int main()
{
cout<<Knapsack()<<endl;//輸出25
system('pause');
return 1;
}2)不需要把背包裝滿，只需要收益最大
使用二維數(shù)組f[i][v]存儲(chǔ)中間狀態(tài)，其中第一維表示物品，第二維表示背包容量
初始化時(shí)，除了f[i][0] = 0（第一列）外，其他全為負(fù)無(wú)窮。
使用一維數(shù)組f[v]存儲(chǔ)中間狀態(tài)，維表示背包容量
原因：如果背包并非必須被裝滿，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。
代碼在最前面已貼，不在此上傳。
一個(gè)常數(shù)優(yōu)化
一維數(shù)組描述狀態(tài)時(shí)的偽代碼：
for i=1..N //枚舉物品
for v=V..0 //枚舉容量，從大到小
f[v]=max{f[v],f[v-weight[i]] cost[i]};觀察可知，對(duì)于第i個(gè)物品，枚舉背包容量下限時(shí)，可以到weight[i]為止。
原因：
1）對(duì)于第i物品，在求f[v]時(shí)，需要使用的狀態(tài)是 v ~ v - weight[i] 這么多，這是由于v取最大容量V時(shí)，使用的狀態(tài)才是v - weight[i]，當(dāng)v不取最大狀態(tài)時(shí)，使用的狀態(tài)肯定是在v ~ v - weight[i]之間的?？梢缘絯eight[i]為止。
2）在到weight[i]為止時(shí)，還可以不進(jìn)行if判斷，擔(dān)心v - weight[i]是否越界
此時(shí)，偽代碼為
for i=1..N //枚舉物品
for v=V..weight[i] //枚舉容量，從大到小
f[v]=max{f[v],f[v-weight[i]] cost[i]};注意，對(duì) f 數(shù)組，如果是檢測(cè)第i個(gè)物品是否能放入，0 ~ weight[i] - 1的這些位置是不會(huì)遍歷到的，則此時(shí)他們?nèi)员硎镜趇 - 1次的狀態(tài)，即二維的f[i - 1][v]。
還可以繼續(xù)優(yōu)化下界為
for i=1..N //枚舉物品
bound=max{V-sum{weight[i..n]},weight[i]}//確定需要枚舉容量的下界
for v=V..bound
f[v]=max{f[v],f[v-weight[i]] cost[i]};原因：
1)網(wǎng)上的說(shuō)法,不太懂,各位大?？梢灾笇?dǎo)下下。
對(duì)于第i次循環(huán)（指外循環(huán)），對(duì)于背包容量v = V(最大)時(shí)，對(duì)于f[v]的值，其實(shí)只要知道f[v-weight[i]]即可。以此類推，對(duì)于背包容量為 j 時(shí)，我們只需要知道到f[v-sum{weight[j..n]}]即可
2)還有人說(shuō)
如果比v-sum{weight[j..n]}這個(gè)小，那么即使后面物品的全要也裝不滿背包。
所以對(duì)于物品i，小于v-sum{weight[j..n]}的v值，無(wú)意義。
總之是不懂。智商啊
作者說(shuō)，當(dāng)V很大是，效果好。
代碼
#include <iostream>
using namespace std;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[V 1] = {0};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[j] = max{f[j],f[j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
int sum = 0;//存儲(chǔ)還未處理物品的總?cè)萘? int bound = 0;
//初始化
memset(f,0,sizeof(f));
for (int i = 1;i <= N;i )
{
sum = weight[i];
}
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
//設(shè)置下界
if (i != 1)
{
sum -= weight[i - 1];
}
bound = Max(V - sum,weight[i]);
for (int j = V;j >= bound;j--) //枚舉背包容量
{
if (f[j] < f[j - weight[i]] value[i])
{
f[j] = f[j - weight[i]] value[i];
}
}
}
return f[V];
}
int main()
{
cout<<Knapsack()<<endl;
system('pause');
return 1;
}輸出方案
一般而言，背包問(wèn)題是要求一個(gè)最優(yōu)值，如果要求輸出這個(gè)最優(yōu)值的方案，可以參照一般動(dòng)態(tài)規(guī)劃問(wèn)題輸出方案的方法：記錄下每個(gè)狀態(tài)的最優(yōu)值是由狀態(tài)轉(zhuǎn)移方程的哪一項(xiàng)推出來(lái)的，換句話說(shuō)，記錄下它是由哪一個(gè)策略推出來(lái)的。便可根據(jù)這條策略找到上一個(gè)狀態(tài)，從上一個(gè)狀態(tài)接著向前推即可。
這里我們首先給出01背包的二維狀態(tài)轉(zhuǎn)移方程
f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] cost[i])
對(duì)于狀態(tài)f[i][v]，它來(lái)自兩種策略，可以是f[i - 1][v],也可以是f[i - 1][v - weight[i]] cost[i]
其中，對(duì)于第二種情況，就是把物品i放入背包了，這里也是我們要找的情況
根據(jù)狀態(tài)轉(zhuǎn)移方程，我們可以給出兩種實(shí)現(xiàn)方法
1) 借助存儲(chǔ)狀態(tài)的數(shù)組，直接根據(jù)狀態(tài)轉(zhuǎn)移方程倒著推，檢測(cè)是否滿足
f[i][v] == f[i - 1][v - weight[i]] value[i]
如果滿足，則把第i件物品放入了，此時(shí)我們要檢測(cè)第i - 1件物品，背包容量為v - weight[i]
不滿足則表示沒(méi)有把第i件物品放入，直接檢測(cè)第i - 1件物品，此時(shí)背包容量還是v
注意，這種方法只適用于存儲(chǔ)狀態(tài)數(shù)組不壓縮的情況。壓縮數(shù)組由于數(shù)據(jù)有覆蓋，不能使用
代碼
#include <iostream>
using namespace std;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[N 1][V 1] = {{0}};
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[i][j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = 1;j <= V;j ) //枚舉背包容量
{
f[i][j] = f[i - 1][j];
if (j >= weight[i])
{
f[i][j] = Max(f[i - 1][j],f[i - 1][j - weight[i]] value[i]);
}
}
}
return f[N][V];
}
/*
輸出順序:逆序輸出物品編號(hào)
注意：這里借助狀態(tài)數(shù)組f[i][v]
使用狀態(tài)轉(zhuǎn)移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] value[i]}
*/
void PrintKnapsack()
{
int i = N;//枚舉物品
int j = V;//枚舉空間
cout<<'加入背包的物品編號(hào):'<<endl;
while(i)
{
if (f[i][j] == f[i - 1][j - weight[i]] value[i])
{
/*if不滿足，表示第i件物品沒(méi)裝入背包,
if條件滿足，表示放入背包了*/
cout<<i<<' ';
j -= weight[i];//此時(shí)容量減少
}
i--;
}
cout<<endl;
}
/*
輸出順序:順序輸出物品編號(hào)
注意：這里借助狀態(tài)數(shù)組f[i][v]
使用狀態(tài)轉(zhuǎn)移方程:f[i][j] = max{f[i - 1][j],f[i - 1][j - weight[i]] value[i]}
*/
void PrintKnapsack_recursion(int i,int j)
{
if (i == 0 || j == 0)
{
return;
}
if (f[i][j] == f[i - 1][j - weight[i]] value[i])
{
PrintKnapsack_recursion(i - 1,j - weight[i]);
cout<<i<<' ';
}
}
int main()
{
cout<<Knapsack()<<endl;
PrintKnapsack();
PrintKnapsack_recursion(N,V);
system('pause');
return 1;
}2) 另外開辟數(shù)組，在求解最大收益時(shí)做標(biāo)記位。求解完最大收益后，根據(jù)這個(gè)新數(shù)組倒著推結(jié)果
思想：對(duì)于現(xiàn)在這個(gè)狀態(tài)的位置，它存儲(chǔ)的是該狀態(tài)上一位置
注意：這種方法均適用存儲(chǔ)狀態(tài)數(shù)組不壓縮 和 壓縮兩種情況
代碼：
#include <iostream>
using namespace std;
const int N = 3;//物品個(gè)數(shù)
const int V = 5;//背包最大容量
int weight[N 1] = {0,3,2,2};//物品重量
int value[N 1] = {0,5,10,20};//物品價(jià)值
int f[V 1] = {0};
int G[N 1][V 1] = {{0}};//求背包序列
int Max(int x,int y)
{
return x > y ? x : y;
}
/*
目標(biāo)：在不超過(guò)背包容量的情況下，最多能獲得多少價(jià)值
子問(wèn)題狀態(tài):f[j]:表示前i件物品放入容量為j的背包得到的最大價(jià)值
狀態(tài)轉(zhuǎn)移方程:f[j] = max{f[j],f[j - weight[i]] value[i]}
初始化:f數(shù)組全設(shè)置為0
*/
int Knapsack()
{
//初始化
memset(f,0,sizeof(f));
memset(G,0,sizeof(G));
//遞推
for (int i = 1;i <= N;i ) //枚舉物品
{
for (int j = V;j >= weight[i];j--) //枚舉背包容量
{
if (f[j] < f[j - weight[i]] value[i])
{
f[j] = f[j - weight[i]] value[i];
G[i][j] = 1;
}
}
}
return f[V];
}
/*
輸出順序:逆序輸出物品編號(hào)
注意：這里另外開辟數(shù)組G[i][v],標(biāo)記上一個(gè)狀態(tài)的位置
G[i][v] = 1:表示物品i放入背包了，上一狀態(tài)為G[i - 1][v - weight[i]]
G[i][v] = 0:表示物品i沒(méi)有放入背包，上一狀態(tài)為G[i - 1][v]
*/
void PrintKnapsack()
{
int i = N;//枚舉物品
int j = V;//枚舉空間
cout<<'加入背包的物品編號(hào):'<<endl;
while(i)
{
if (G[i][j] == 1)
{
/*if不滿足，表示第i件物品沒(méi)裝入背包,
if條件滿足，表示放入背包了*/
cout<<i<<' ';
j -= weight[i];//此時(shí)容量減少
}
i--;
}
cout<<endl;
}
/*
輸出順序:順序輸出物品編號(hào)
注意：這里另外開辟數(shù)組G[i][v],標(biāo)記上一個(gè)狀態(tài)的位置
G[i][v] = 1:表示物品i放入背包了，上一狀態(tài)為G[i - 1][v - weight[i]]
G[i][v] = 0:表示物品i沒(méi)有放入背包，上一狀態(tài)為G[i - 1][v]
*/
void PrintKnapsack_recursion(int i,int j)
{
if (i == 0 || j == 0)
{
return;
}
if (G[i][j] == 1)
{
PrintKnapsack_recursion(i - 1,j - weight[i]);
cout<<i<<' ';
}
}
int main()
{
cout<<Knapsack()<<endl;
PrintKnapsack();
PrintKnapsack_recursion(N,V);
system('pause');
return 1;
}小結(jié)：
01 背包問(wèn)題是最基本的背包問(wèn)題，它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想。另外，別的類型的背包問(wèn)題往往也可以轉(zhuǎn)換成01 背包問(wèn)題求解。故一定要仔細(xì)體會(huì)上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及空間復(fù)雜度怎樣被優(yōu)化。
聯(lián)系客服
