1、深入理解背包相關(guān)問題。

2、能正確設(shè)計相應(yīng)的算法，解決實際問題。

? 3、掌握算法時間復(fù)雜度分析。

二、實驗要求

1. 用3種方法求解0-1背包問題（貪心算法、動態(tài)規(guī)劃、分支限界法），獲得精確最優(yōu)解或近似最優(yōu)解均可。
2. 通過一個規(guī)模較大的實例比較不同方法的求解速度，分析不同算法的時間復(fù)雜度，并分析是否能獲得最優(yōu)解。
3. 實驗結(jié)果跟實驗設(shè)置的參數(shù)（如：背包容量、物品的體積）關(guān)系很大，簡要分析參數(shù)對結(jié)果的影響。

三、實驗原理

1.動態(tài)規(guī)劃解0-1背包原理：

動態(tài)規(guī)劃基本思想是將帶求解的問題分解成若干子問題，先求解子問題，再結(jié)合這些子問題的解得到原問題的解。

用動態(tài)規(guī)劃算法解0-1背包原理為：設(shè)0-1背包問題的子問題

max∑vkxk,(k=i-n)???? ∑wkxk<=j

????????????????????? xk∈{0,1}? i<=k<=n

的最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選擇物品為i,i+1,···，n時0-1背包問題的最優(yōu)值，由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i,j)的遞歸式如下：

m(i,j)=? ???max{m(i+1,j),m(i+1,j-wi+vi)}? j>=wi

????????? m(i+1,j)???? 0<=j<=wn

m(n,j)=??? vn? j>=wn

1. 0<=j<wn

所以基于以上討論，當(dāng)wi(1<=i<=n)為正整數(shù)時，用二維數(shù)組m[][]來存儲m(i,j)的值，最后m[1][c]給出所要求的0-1背包的最優(yōu)值，相應(yīng)的最優(yōu)解有Traceback函數(shù)計算如下：如果m[1][c]=m[2][c],則x1=0,否則x1=1。當(dāng)x1=0時，由m[2][c]繼續(xù)構(gòu)造最優(yōu)解。當(dāng)x1=1時，由m[2][c-w1]繼續(xù)構(gòu)造最優(yōu)解。以此類推，可構(gòu)造出相應(yīng)的最優(yōu)解（x1,x2,···xn）。

2.貪心算法解0-1背包原理

貪心算法是一種只考慮當(dāng)前最優(yōu)的算法，其不從總體上考慮，所以貪心算法不是對所有問題都能求得整體最優(yōu)解，像本實驗中的0-1背包問題，用貪心算法一般求得的是局部最優(yōu)解，用貪心算法解0-1背包問題原理如下：

首先我們按照物品的單位重量價值來進(jìn)行排序，然后按照單位重量價值從高到低依次進(jìn)行選擇，若其能裝入背包則將其裝入，不能則繼續(xù)判斷下一個直至所有物品都判斷完，就得到了問題的一個解。但是對于0-1背包問題，用貪心算法并不能保證最終可以將背包裝滿，部分剩余的空間使得單位重量背包空間的價值降低了，這也是用貪心算法一般無法求得0-1背包最優(yōu)解的原因。

3.分支限界發(fā)解0-1背包問題原理

本次實驗中用優(yōu)先隊列式分支限界法求解0-1背包問題，原理如下：（1）分支限界法通常是用廣度優(yōu)先或最大效益優(yōu)先方式搜索問題的解空間樹，而對于本次實驗中求解的0-1背包問題的解空間樹是一顆子集樹；（2）在分支限界法中還有一個活結(jié)點表，活結(jié)點表中的每個活結(jié)點只有一次機(jī)會成為擴(kuò)展結(jié)點，一旦成為擴(kuò)展結(jié)點就一次性產(chǎn)生其所有兒子結(jié)點，在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余的兒子結(jié)點則被加入到活結(jié)點中表。而對于0-1背包問題中的每個活結(jié)點只有兩個兒子結(jié)點，分別表示對該物品選取或舍去；對于一個兒子結(jié)點是否能加入到活結(jié)點表中有兩個條件用于判斷，一個是約束函數(shù)判斷能否滿足背包容量約束，另一個是限界函數(shù)判斷是否可能得到最優(yōu)解。（3）為了能夠比較快速的找到0-1背包問題的解，每次選取下一個活結(jié)點成為擴(kuò)展結(jié)點的判斷依據(jù)是當(dāng)前情況下最有可能找到最優(yōu)解的下一個結(jié)點。所以每次選擇擴(kuò)展結(jié)點采取如下方法：當(dāng)前情況下，在活結(jié)點表中選擇活結(jié)點的上界uprofit(通過限界函數(shù)Bound求出)最大的活結(jié)點成為當(dāng)前的擴(kuò)展結(jié)點。這一過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。此過程體現(xiàn)出分支限界法以“最大效益優(yōu)先”方式進(jìn)行。（4）為了在活結(jié)點表中選擇擁有最大的上界uprofit的活結(jié)點，在活結(jié)點表上實現(xiàn)優(yōu)先隊列。

（5）通過上述第3點，可以求出0-1背包問題的最優(yōu)值。為了求出0-1背包問題的最優(yōu)解，對于每一個在 活結(jié)點表中的活結(jié)點創(chuàng)建一個樹結(jié)點，樹節(jié)點需要反映該結(jié)點的父節(jié)點和是否有左孩子（有左孩子 表示物品i選取了，沒有左孩子表示物品i舍去了）。因此，可以構(gòu)造一顆子集樹，最優(yōu)解就是從樹根 到葉子結(jié)點的路徑，子集樹的第i層的所有結(jié)點就是在不同情況下對物品i的取舍結(jié)點。構(gòu)造最優(yōu)解的 順序是從葉子結(jié)點到根結(jié)點的過程。

4.三種方法求解速度的比較

三種方法的求解速度w我們可以通過比較三種方法的求解所需時間來實現(xiàn)，而求解所需要的時間在C++中也較為容易實現(xiàn)，通過cout << "The run time is:" << (double)clock() /CLOCKS_PER_SEC<< "s" << endl;這句語句即可獲得所需時間。

四、實驗結(jié)果

1.首先，先對一簡單的實例，用三種方法進(jìn)行求解，該簡單實例是在物品種類n=5,背包容量c=10,價值數(shù)組為v={6,3,5,4,6};重量數(shù)組w={2,2,6,5,4};

從上面三個結(jié)果的截圖我們可以發(fā)現(xiàn)對于數(shù)據(jù)比較少的簡單的案例三種方法所用時間基本相差不大，并且因為所選案例關(guān)系，三種方法都求得了最優(yōu)解，下面換一個數(shù)據(jù)少的案例，來體現(xiàn)貪心算法不一定能求得最優(yōu)解的性質(zhì)：n=4,背包容量c=15,價值數(shù)組為v={5 6 7 9};重量數(shù)組w={2 3 5 7};

動態(tài)規(guī)劃算法結(jié)果：

貪心算法結(jié)果：

（輸入見圖）

分支限界結(jié)果：

（輸入見圖）

2.對大數(shù)據(jù)求解

下面用一組較大規(guī)模的數(shù)據(jù)，來進(jìn)行求解：

這組實例設(shè)置如下：int n=50; int c=100;

int v[50]={3,5,4,5,6,3,4,7,6,2,3,5,6,7,8,9,7,10,3,4,5,1,2,6,7,9,5,6,7,9,6,4,3,2,3,5,6,7,8,6,4,2,1,3,4,6,7,8,9,2};

int w[50]={6,5,4,3,5,6,7,4,6,7,7,8,4,3,4,5,6,8,3,4,2,5,6,7,8,5,6,4,3,3,5,6,8,9,4,2,5,6,7,8,9,3,2,4,6,7,8,9,9,6};

下面是用三種算法求解的結(jié)果截圖：

動態(tài)規(guī)劃：

貪心算法：

分支限界法：

1.據(jù)所學(xué)貪心算法時間復(fù)雜度只有O（n）,而考慮排序的話，就會耗費(fèi)較多時間，本次實驗中我采用了選擇排序，時間復(fù)雜度較高，不過因為數(shù)據(jù)量不夠大，且所用數(shù)據(jù)較為有序，所以貪心算法所用時間還是比較短的。2.動態(tài)規(guī)劃算法的時間復(fù)雜度為O(n*c),當(dāng)c較大時，其時間復(fù)雜度會比較高。3.分支限界法時間復(fù)雜度為O(2^n)，其效率不高。所以總的來看貪心算法還是比較快的，雖然其不一定能求得最優(yōu)解，但其可以用較短時間來求一個近似解。

心得體會

本次實驗主要是用三種方法來求解0-1背包問題，通過本次實驗我對0-1背包問題有了更深刻的認(rèn)識，并且對動態(tài)規(guī)劃、貪心算法、分支限界三種方法也有了充分了解，對其適用的問題也較為清晰，像動態(tài)規(guī)劃最重要的部分就是二維數(shù)組的構(gòu)建還有要理解狀態(tài)方程，貪心算法適用于最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題，并且動態(tài)規(guī)劃和貪心算法的主要區(qū)別就在于動態(tài)規(guī)劃依賴于子問題的求解而貪心算法不需要，并且通過此次實驗，我對于貪心算法不一定能求得最優(yōu)解也有了更深刻的認(rèn)識，貪心算法是求局部最優(yōu)解的很好的算法，對于求最優(yōu)解并不是最好的選擇，同時通過本次實驗我對三種方法的時間復(fù)雜度也較為熟練的掌握。

附錄

動態(tài)規(guī)劃

#include<stdio.h>
#include<iostream>
using?namespace?std;
#define?max(x,y)?((x)>(y)?(x):(y))
#define?MAXN?30 //最多物品數(shù)
#define?MAXW?100 //最大限制重量
//問題表示
int?n,?W; //n個數(shù)，W容量
int?w[MAXN],?v[MAXN]; //物品重量和價值
//求解結(jié)果表示
int?dp[MAXN][MAXW];
int?x[MAXN];
int?bestp; //存放最優(yōu)解的總價值
//用動態(tài)規(guī)劃法求0/1背包問題
void?Knap()
{
int?i,?r;
for?(i?=?0;?i?<=?n;?i++) //置邊界條件dp[i][0]?=?0
dp[i][0]?=?0;
for?(r?=?0;?r?<=?W;?r++) //置邊界條件dp[0][r]?=?0
dp[0][r]?=?0;
for?(i?=?1;?i?<=?n;?i++)?{
for?(r?=?1;?r?<=?W;?r++)?{
if?(r?<?w[i])
dp[i][r]?=?dp[i?-?1][r];
else
dp[i][r]?=?max(dp[i?-?1][r],?dp[i?-?1][r?-?w[i]]?+?v[i]);
}
}
}
void?Buildx() //回推求最優(yōu)解
{
int?i?=?n,?r?=?W;
bestp?=?0;
while?(i?>=?0)?{
if?(dp[i][r]?!=?dp[i?-?1][r])?{
x[i]?=?1;
bestp?+=?v[i];
r?=?r?-?w[i];
}
else
x[i]?=?0;
i--;
}
}
int?main()?{
cout?<<?"輸入物品個數(shù)n:";?cin?>>?n;
cout?<<?"輸入最大容量W:";?cin?>>?W;
cout?<<?"依次輸入每個物品的重量w和價值v，用空格分開：";
for?(int?i?=?1;?i?<=?n;?i++)?{
cin?>>?w[i]?>>?v[i];
}
Knap();
Buildx();
printf("最優(yōu)方案\n");
printf("選取物品為：");
for?(int?i?=?1;?i?<=?n;?i++)
if?(x[i]?==?1)
printf("%d?",?i);
printf("\n");
printf("總價值=%d\n",?bestp);
return?0;
}貪心：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using?namespace?std;
#define?MAXN?51
int?n;
int?W;
struct?NodeType
{
int?w;
int?v;
int?p; //性價比p=v/w
bool?operator<(const?NodeType&?s)const
{
return?p?>?s.p;
}
};
NodeType?A[MAXN];
int?maxv;
int?x[MAXN];
void?Knap() //求解背包問題并返回總價值
{
maxv?=?0; //maxv初始化為0
int?weight?=?W; //背包中能裝入的余下重量
memset(x,?0,?sizeof(x)); //初始化x向量
int?i?=?1;
while?(A[i].w?<=?weight) //物品i能夠全部裝入背包時，循環(huán)
{
x[i]?=?1; //裝入物品i
weight?-=?A[i].w; //減少背包中能裝入的余下重量
maxv?+=?A[i].v; //計算裝入物品i后的總價值
i++;
}
}
void?disp_bestx()?{
int?sumw?=?0;
cout?<<?"放入購物車的物品序號為：";
for?(int?j?=?1;?j?<=?n;?j++)?{
if?(x[j]?==?1)?{
cout?<<?j?<<?"?";
sumw?+=?A[j].w;
}
}
cout?<<?endl;
cout?<<?"放入購物車的物品最大價值為："?<<?maxv?<<?"，總重量為："?<<?sumw?<<?endl;
}
int?main()
{
cout?<<?"輸入物品個數(shù)n:";?cin?>>?n;
cout?<<?"輸入購物車容量W:";?cin?>>?W;
cout?<<?"依次輸入每個物品的重量w和價值v，用空格分開："?<<?endl;;
for?(int?i?=?1;?i?<=?n;?i++)?{
cin?>>?A[i].w?>>?A[i].v;
}
for?(int?i?=?1;?i?<=?n;?i++)?{
A[i].p?=?A[i].v?/?A[i].w;
}
sort(A?+?1,?A?+?1?+?n);
Knap();
disp_bestx();
return?0;
}分支限界

分支限界法：
#include?<iostream>
#define?N?30
using?namespace?std;
int?n;double?W;?//n個數(shù)，W容量
double?w[N];double?v[N];??//物品重量和價值
bool?x[N];
bool?best_x[N];?//存儲最優(yōu)方案
double?now_v;???//當(dāng)前價值
double?remain_v;????//剩余價值
double?now_w;???//當(dāng)前容量
double?best_v;??//最優(yōu)價值
double?Bound(int?k)?????//計算分枝結(jié)點k的上界
{
????remain_v?=?0;
????while?(k?<=?n)?{
????????remain_v?+=?v[k];
????????k++;
????}
????return?remain_v?+?now_v;
}
void?Backtrack(int?t)
{
????if?(t?>?n)?{??//是否到達(dá)葉節(jié)點
????????for?(int?i?=?1;?i?<=?n;?i++)?{
????????????best_x[i]?=?x[i];???//記錄回溯的最優(yōu)情況
????????}
????????best_v?=?now_v;?//記錄回溯中的最優(yōu)價值
????????return;
????}
????if?(now_w?+?w[t]?<=?W)?{??//約束條件，是否放入。放入考慮左子樹，否則考慮右子樹
????????x[t]?=?1;
????????now_w?+=?w[t];
????????now_v?+=?v[t];
????????Backtrack(t?+?1);?//進(jìn)行下一個節(jié)點的分析
????????now_w?-=?w[t];??//在到達(dá)葉節(jié)點后進(jìn)行回溯
????????now_v?-=?v[t];
????}
????if?(Bound(t?+?1)?>?best_v)?{????//限界條件，是否剪枝。若放入t后不滿足約束條件則進(jìn)行到此處，然后判斷若當(dāng)前價值加剩余價值都達(dá)不到最優(yōu)，則沒必要進(jìn)行下去
????????x[t]?=?0;
????????Backtrack(t?+?1);
????}
}
void?Knapsack(double?W,?int?n)
{
????double?sum_w?=?0;
????double?sum_v?=?0;
????best_v?=?0;
????for?(int?i?=?0;?i?<?n;?i++)?{
????????sum_w?+=?w[i];
????????sum_v?+=?v[i];
????}
????Backtrack(1);
????cout?<<?"放入購物車的物品最大價值為："?<<?best_v?<<?endl;
????cout?<<?"放入購物車的物品序號為："?<<?endl;
????for?(int?i?=?1;?i?<=?n;?i++)?{
????????if(x[i]?==?1)
????????????cout?<<?i?<<?"?";
????}
}
int?main()
{
????cout?<<?"輸入物品個數(shù)n:";?cin?>>?n;
????cout?<<?"輸入購物車容量W:";?cin?>>?W;
????cout?<<?"依次輸入每個物品的重量w和價值v，用空格分開：\n";
????for?(int?i?=?1;?i?<=?n;?i++)?{
????????cin?>>?w[i]?>>?v[i];
????}
????Knapsack(W,?n);
????return?0;
}文章來源地址http://www.zghlxwxcb.cn/news/detail-787756.html

到了這里，關(guān)于01背包問題三種解決（貪心動態(tài)規(guī)劃分支限界）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！