[ 本帖最后由 51黑tt 于 2016-3-5 20:08 編輯 ]\n\n作為算法設(shè)計分析的經(jīng)典問題，已經(jīng)寫過一次了，不過實現(xiàn)的方法不同，這次是回溯法解決問題。問題還是老問題，但是方法是新的！ 哈哈
在這里再簡單寫一下問題要求：
給定n中物品和一個容量為c的背包，物品i的重量為Wi,其價值為Vi,0-1背包問題是如何選擇裝入背包的物品（物品不可分割），使得裝入背包的物品的價值為最大。
1.題目分析：
考慮到每種物品只有2 種選擇，即裝入背包或不裝入背包，并且物品數(shù)和背包容量已給定，要計算裝入背包物品的最大價值和最優(yōu)裝入方案，可用回溯法搜索子集樹的算法進行求解。
2.算法設(shè)計：
a. 物品有n種，背包容量為C，分別用p和w存儲第i種物品的價值和重量，用
x標記第i種物品是否裝入背包，用bestx存儲第i種物品的最優(yōu)裝載方案；
b. 用遞歸函數(shù)Backtrack (i,cp,cw)來實現(xiàn)回溯法搜索子集樹（形式參數(shù)i表示遞歸深
度，n用來控制遞歸深度，形式參數(shù)cp和cw表示當前總價值和總重量，bestp表示當前
最優(yōu)總價值）：
① 若i >n，則算法搜索到一個葉結(jié)點，判斷當前總價值是否最優(yōu)：
1> 若cp>bestp，更新當前最優(yōu)總價值為當前總價值（即bestp=cp），更新
裝載方案（即bestx=x( 1≤i≤n)）；
② 采用for循環(huán)對物品i裝與不裝兩種情況進行討論（0≤j≤1）：
1> x=j；
2> 若總重量不大于背包容量（即cw+x*w<=c），則更新當前總價 br=""> 值和總重量（即cw+=w*x,cp+=p*x）, 對物品i+1調(diào)用遞歸函
數(shù)Backtrack(i+1,cp,cw) 繼續(xù)進行裝載；
3> 函數(shù)Backtrack(i+1,cp,cw)調(diào)用結(jié)束后則返回當前總價值和總重量
（即 cw-=w*x,cp-=p*x）；
4> 當j>1時，for循環(huán)結(jié)束；
③ 當i=1時，若已測試完所有裝載方案，外層調(diào)用就全部結(jié)束；
c. 主函數(shù)調(diào)用一次backtrack(1,0,0)即可完成整個回溯搜索過程，最終得到的bestp和bestx即為所求最大總價值和最優(yōu)裝載方案。
最后給出代碼。很不幸的是我自己沒有寫出來源碼，這個是從網(wǎng)絡(luò)找到后又經(jīng)過自己改寫的。。。。。技術(shù)不夠沒辦法啊
#include<stdio.h>
int n,c,bestp;//物品的個數(shù)，背包的容量，最大價值
int p[10000],w[10000],x[10000],bestx[10000];//物品的價值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況
void Backtrack(int i,int cp,int cw)
{ //cw當前包內(nèi)物品重量，cp當前包內(nèi)物品價值
int j;
if(i>n)//回溯結(jié)束
{
if(cp>bestp)
{
bestp=cp;
for(i=0;i<=n;i++) bestx[i]=x[i];
}
}
else
for(j=0;j<=1;j++)
{
x[i]=j;
if(cw+x[i]*w[i]<=c)
{
cw+=w[i]*x[i];
cp+=p[i]*x[i];
Backtrack(i+1,cp,cw);
cw-=w[i]*x[i];
cp-=p[i]*x[i];
}
}
}
int main()
{
int i;
bestp=0;
printf("請輸入背包最大容量:\n");
scanf("%d",&c);
printf("請輸入物品個數(shù):\n");
scanf("%d",&n);
printf("請依次輸入物品的重量:\n");
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
printf("請依次輸入物品的價值:\n");
for(i=1;i<=n;i++)
scanf("%d",&p[i]);
Backtrack(1,0,0);
printf("最大價值為:\n");
printf("%d\n",bestp);
printf("被選中的物品依次是(0表示未選中，1表示選中)\n");
for(i=1;i<=n;i++)
printf("%d ",bestx[i]);
printf("\n");
return 0;
}
|
