從Tianyi Cui童鞋《背包問題講9》。細(xì)微的變化，很容易理解。

01背包問題描寫敘述

已知:有一個(gè)容量為V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。

限制:每種物品僅僅有一件，能夠選擇放或者不放

問題:在不超過背包容量的情況下，最多能獲得多少價(jià)值或收益

相似問題:在恰好裝滿背包的情況下，最多能獲得多少價(jià)值或收益

這里，我們先討論在不超過背包容量的情況下。最多能獲得多少價(jià)值或收益。

基本思路

01背包的特點(diǎ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])

分析

考慮我們的子問題，將前i件物品放到容量為v的背包中。若我們僅僅考慮第i件物品時(shí)。它有兩種選擇，放或者不放。

1) 假設(shè)第i件物品不放入背包中。那么問題就轉(zhuǎn)換為：將前i - 1件物品放到容量為v的背包中。帶來的收益f[i - 1][v]

2) 假設(shè)第i件物品能放入背包中。那么問題就轉(zhuǎn)換為：將前i - 1件物品放到容量為v - weight[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)：在不超過背包容量的情況下，最多能獲得多少價(jià)值子問題狀態(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)。當(dāng)中，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é)果

分析

我們?nèi)缃袷褂胒[v]保存中間狀態(tài)。我們想要達(dá)到的效果是。第i次循環(huán)后，f[v]中存儲(chǔ)的是前i個(gè)物體放到容量v時(shí)的最大價(jià)值

在回想下之前講過的狀態(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]]，因?yàn)槲覀兪褂枚S數(shù)組保存中間狀態(tài)，所以能夠直接取出這兩個(gè)狀態(tài)。

當(dāng)我們使用一維數(shù)組存儲(chǔ)狀態(tài)時(shí)，f[v]表示。在運(yùn)行i次循環(huán)后(此時(shí)已經(jīng)處理i個(gè)物品)。前i個(gè)物體放到容量v時(shí)的最大價(jià)值。即之前的f[i][v]。與二維相比較，它把第一維隱去了，可是二者表達(dá)的含義還是同樣的，僅僅只是針對不同的i。f[v]一直在反復(fù)使用。所以。也會(huì)出現(xiàn)第i次循環(huán)可能會(huì)覆蓋第i - 1次循環(huán)的結(jié)果。

為了求f[v],我們須要知道，前i - 1個(gè)物品放到容量v的背包中帶來的收益，即之前的f[i - 1][v]? 和 前i - 1件物品放到容量為v - weight[i]的背包中帶來的收益，即之前的f[i - 1][v - weight[i]] + cost[i]。

難點(diǎn)：由于我們僅僅使用一維數(shù)組存儲(chǔ)，則在求這兩個(gè)子問題時(shí)就沒有直接取出那么方便了。由于，第i次循環(huán)可能會(huì)覆蓋第i - 1次循環(huán)的結(jié)果。

如今我們來求這兩個(gè)值

1）前i - 1個(gè)物品放到容量v的背包中帶來的收益。即之前的f[i - 1][v] ：

因?yàn)?#xff0c;在運(yùn)行在i次循環(huán)時(shí)。f[v]存儲(chǔ)的是前i個(gè)物體放到容量v時(shí)的最大價(jià)值。在求前i個(gè)物體放到容量v時(shí)的最大價(jià)值(即之前的f[i][v])時(shí)，我們是正在運(yùn)行第 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]的背包中帶來的收益，即之前的f[i - 1][v - weight[i]] + cost[i]

因?yàn)?#xff0c;在運(yùn)行第i次循環(huán)前。f[0 ~ V]中保存的是第i - 1次循環(huán)的結(jié)果。即是前i - 1個(gè)物體分別放到容量0 ~ V時(shí)的最大價(jià)值，即f[i - 1][0 ~ V]。

則。在運(yùn)行第i次循環(huán)前。f 數(shù)組中v - weight[i]的位置存儲(chǔ)就是我們要找的 前i - 1件物品放到容量為v - weight[i]的背包中帶來的收益 (即之前的f[i - 1][v - weight[i]])，這里如果物品是從數(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可知，在運(yùn)行第 i 次循環(huán)時(shí)。須要把背包容量由V..0都要遍歷一遍，檢測第 i 件物品能否放。

逆序枚舉容量的原因：

注意一點(diǎn)，我們是由第 i - 1 次循環(huán)的兩個(gè)狀態(tài)推出 第 i 個(gè)狀態(tài)的。并且 v? > v - weight[i]，則對于第i次循環(huán)，背包容量僅僅有當(dāng)V..0循環(huán)時(shí)。才會(huì)先處理背包容量為v的狀況。后處理背包容量為 v-weight[i] 的情況。

詳細(xì)來說。因?yàn)?#xff0c;在運(yùn)行v時(shí)，還沒運(yùn)行到v - weight[i]的，因此。f[v - weight[i]]保存的還是第i - 1次循環(huán)的結(jié)果。

即在運(yùn)行第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]]。

相反。假設(shè)在運(yùn)行第 i 次循環(huán)時(shí)，背包容量依照0..V的順序遍歷一遍。來檢測第 i 件物品能否放。此時(shí)在運(yùn)行第i次循環(huán) 且 背包容量為v時(shí)，此時(shí)的f[v]存儲(chǔ)的是 f[i - 1][v] 。可是，此時(shí)f[v-weight[i]]存儲(chǔ)的是f[i][v-weight[i]]。

由于。v? > v - weight[i]。第i次循環(huán)中。運(yùn)行背包容量為v時(shí)。容量為v - weight[i]的背包已經(jīng)計(jì)算過，即f[v - weight[i]]中存儲(chǔ)的是f[i][v - weight[i]]。

即，對于01背包，依照增序枚舉背包容量是不正確的。

代碼

#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)：在不超過背包容量的情況下。最多能獲得多少價(jià)值子問題狀態(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ì)不超過背包容量

而逆序枚舉背包容量：背包中的物品至多裝一次，使價(jià)值最大，當(dāng)然不會(huì)不超過背包容量

我們首先舉例說明：

逆序枚舉物品

當(dāng)i = 2，我們要求 f [5]：表示檢測物品2放入容量為5的背包的最大收益

上圖表示，當(dāng)i = 2。求f[5]時(shí)f數(shù)組的狀況，

橙色為數(shù)組如今存儲(chǔ)的值，這些值是i = 1時(shí)(上一次循環(huán))存入數(shù)組 f 的。相當(dāng)于f[i - 1][v]

而黃色使我們要求的值，在求f[5]之前，f[5]= 5。即f[i - 1][5] = 5

如今要求 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]：表示檢測物品2放入容量為5的背包的最大收益

上圖表示，當(dāng)i = 2，求f[5]時(shí)f數(shù)組的狀況，

橙色為數(shù)組如今存儲(chǔ)的值。這些值是i = 2時(shí)(本次循環(huán))存入數(shù)組 f 的。

相當(dāng)于f[i][v]

這是因?yàn)椤Ｎ覀兪窃鲂虮闅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

如今要求 i = 2 時(shí)的f[5] = f[5 - 2] + 10 =10+ 10 = 20 > ?f[i - 1][5] = 5

故，f[5] = 20；

當(dāng)中引用的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è)角度說。

在檢測 背包容量為5時(shí)。看物品2是否增加

由狀態(tài)轉(zhuǎn)移方程可知。我們f[5]須要引用自己本身和f[3]

因?yàn)楸嘲萘繛?時(shí)，能夠裝入物品2，且收益比之前的大。所以放入背包了。

在檢測f[5]時(shí)，肯定要加上物品2的收益，而f[5]在引用f[3]時(shí)，f[3]時(shí)已經(jīng)加過一次物品2。

因此。在枚舉背包容量時(shí)。物品2會(huì)增加多次。

進(jìn)一步說：

我們觀察一維狀態(tài)轉(zhuǎn)移方程：

f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + cost[i])

首先我們明白三個(gè)問題

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) 對于物品i。我們在枚舉背包容量時(shí)，僅僅要背包容量能裝下物品i 且 收益比原來的大。就會(huì)成功放入物品i。

詳細(xì)來說，枚舉背包容量時(shí)，是以遞增的順序的話，因?yàn)?v - weight[i] < v,則會(huì)先計(jì)算 v - weight[i]。在背包容量為v - weight[i]時(shí)，一旦裝入了物品i。因?yàn)榍骹[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í)上，順序枚舉容量是全然背包問題最簡捷的解決方式。

?

初始化的細(xì)節(jié)問題

求最優(yōu)解的背包問題時(shí)，有兩種問法：

1)在不超過背包容量的情況下。最多能獲得多少價(jià)值

2)在恰好裝滿背包的情況下，最多能獲得多少價(jià)值

基本的差別為是否要求恰好裝滿背包。但這兩種問法的實(shí)現(xiàn)方法是在初始化的時(shí)候有所不同。

1)恰好裝滿背包的情況：使用二維數(shù)組f[i][v]存儲(chǔ)中間狀態(tài)。當(dāng)中第一維表示物品。第二維表示背包容量

初始化時(shí)。除了f[i][0] = 0（第一列）外。其它全為負(fù)無窮。

原因：初始化 f 數(shù)組就是表示：在沒有不論什么物品能夠放入背包時(shí)的合法狀態(tài)。

對于恰好裝滿背包，僅僅有背包容量為 0（第一列）。能夠什么物品都不裝就能裝滿，這樣的情況是合法情況，此時(shí)價(jià)值為0。其它f[0][v]（第一列）是都不能裝滿的，此時(shí)有容量沒物品。

而其它位置（除去第一行和第一列的位置），我們?yōu)榱嗽谟?jì)算中比較最大值，也要初始化為負(fù)無窮。我們從程序的角度上看，我們僅僅同意裝入背包物品的序列的起始位置是從第一列開始，這些起始位置都是合法位置。且能恰好裝滿的情況收益均為正值，到f[N][V]終止。

注意，我們盡管是求恰好裝滿，還是須要枚舉全部能夠裝入背包的物品，僅僅要能裝入，還需裝入。收益有添加。僅僅只是。因?yàn)榍『醚b滿的物品的序列肯定是從第一列某行開始的，且之后的收益肯定是正值。對于非恰好裝滿的物品序列，事實(shí)上位置肯定是從第一行某位置開始的，因?yàn)榇藭r(shí)被初始化為負(fù)無窮。在和那些恰好裝滿物品序列帶來的價(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à)值子問題狀態(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;//輸出25system("pause");return 1; }

使用一維數(shù)組f[v]存儲(chǔ)中間狀態(tài)，維表示背包容量

初始化時(shí)，除了f[0] = 0。其它全為負(fù)無窮。

原因：僅僅有容量為0 的背包能夠什么物品都不裝就能裝滿，此時(shí)價(jià)值為0。其他容量的背包均沒有合法的解，屬于沒有定義的狀態(tài)，應(yīng)該被賦值為負(fù)無窮了

代碼

#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à)值子問題狀態(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;//輸出25system("pause");return 1; }

2)不須要把背包裝滿，僅僅須要收益最大

使用二維數(shù)組f[i][v]存儲(chǔ)中間狀態(tài)。當(dāng)中第一維表示物品。第二維表示背包容量

初始化時(shí)，除了f[i][0] = 0（第一列）外。其它全為負(fù)無窮。

使用一維數(shù)組f[v]存儲(chǔ)中間狀態(tài)，維表示背包容量

原因：假設(shè)背包并不是必須被裝滿。那么不論什么容量的背包都有一個(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]};

觀察可知，對于第i個(gè)物品，枚舉背包容量下限時(shí)，能夠到weight[i]為止。

原因：

1）對于第i物品。在求f[v]時(shí)，須要使用的狀態(tài)是 v ~ v - ?weight[i] 這么多。這是因?yàn)関取最大容量V時(shí)，使用的狀態(tài)才是v - weight[i]，當(dāng)v不取最大狀態(tài)時(shí)。使用的狀態(tài)肯定是在v ~ v - ?weight[i]之間的。能夠到weight[i]為止。

2）在到weight[i]為止時(shí)，還能夠不進(jìn)行if推斷，操心v - ?weight[i]是否越界

此時(shí)，偽代碼為

for i=1..N //枚舉物品for v=V..weight[i] //枚舉容量，從大到小f[v]=max{f[v],f[v-weight[i]] + cost[i]};

注意。對 f 數(shù)組，假設(shè)是檢測第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..boundf[v]=max{f[v],f[v-weight[i]] + cost[i]};

原因：

1)網(wǎng)上的說法,不太懂,各位大牛能夠指導(dǎo)下下。

對于第i次循環(huán)（指外循環(huán)），對于背包容量v = V(最大)時(shí)。對于f[v]的值，事實(shí)上僅僅要知道f[v-weight[i]]就可以。以此類推。對于背包容量為 j 時(shí)，我們僅僅須要知道到f[v-sum{weight[j..n]}]就可以

2)還有人說

假設(shè)比v-sum{weight[j..n]}這個(gè)小，那么即使后面物品的全要也裝不滿背包。

所以對于物品i。小于v-sum{weight[j..n]}的v值，無意義。

總之是不懂。智商啊

作者說。當(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)：在不超過背包容量的情況下。最多能獲得多少價(jià)值子問題狀態(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è)萘縤nt 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; }

?輸出方案

一般而言，背包問題是要求一個(gè)最優(yōu)值，假設(shè)要求輸出這個(gè)最優(yōu)值的方案，能夠參照一般動(dòng)態(tài)規(guī)劃問題輸出方案的方法：記錄下每一個(gè)狀態(tài)的最優(yōu)值是由狀態(tài)轉(zhuǎn)移方程的哪一項(xiàng)推出來的，換句話說，記錄下它是由哪一個(gè)策略推出來的。便可依據(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])

對于狀態(tài)f[i][v]，它來自兩種策略，能夠是f[i - 1][v],也能夠是f[i - 1][v - weight[i]] + cost[i]

當(dāng)中，對于另外一種情況，就是把物品i放入背包了。這里也是我們要找的情況

依據(jù)狀態(tài)轉(zhuǎn)移方程，我們能夠給出兩種實(shí)現(xiàn)方法

1) 借助存儲(chǔ)狀態(tài)的數(shù)組。直接依據(jù)狀態(tài)轉(zhuǎn)移方程倒著推，檢測是否滿足

f[i][v] == f[i - 1][v - weight[i]] + value[i]

假設(shè)滿足。則把第i件物品放入了，此時(shí)我們要檢測第i - 1件物品。背包容量為v - weight[i]

不滿足則表示沒有把第i件物品放入，直接檢測第i - 1件物品，此時(shí)背包容量還是v

注意，這樣的方法僅僅適用于存儲(chǔ)狀態(tài)數(shù)組不壓縮的情況。壓縮數(shù)組因?yàn)閿?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)：在不超過背包容量的情況下，最多能獲得多少價(jià)值子問題狀態(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件物品沒裝入背包,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é)果

思想：對于如今這個(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)：在不超過背包容量的情況下。最多能獲得多少價(jià)值 子問題狀態(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沒有放入背包，上一狀態(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件物品沒裝入背包, 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沒有放入背包。上一狀態(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 背包背包問題是主要問題，它包括設(shè)計(jì)狀態(tài)背包問題、最基本的思想公式。其他。其他類型的背包問題常常可以轉(zhuǎn)化成01 背包問題。

我們必須小心經(jīng)驗(yàn)可借鑒的方法的基本思想頂部，含義狀態(tài)轉(zhuǎn)移方程，如何優(yōu)化空間復(fù)雜度。

轉(zhuǎn)載于:https://www.cnblogs.com/hrhguanli/p/4560677.html

總結(jié)

以上是生活随笔為你收集整理的九背包上的发言稿_01背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。