【實(shí)驗(yàn)?zāi)康摹?/font>
學(xué)習(xí)掌握回溯算法。
?
【實(shí)驗(yàn)內(nèi)容】
用回溯法求解
0
—
1
背包問題，并輸出問題的最優(yōu)解。
0
—
1
背包問題描述如下：
給定
n
種物品和一背包。物品
i
的重量是
Wi
，其價(jià)值為
Vi
，背包的容量是
c
，問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大。
?
【實(shí)驗(yàn)條件】
Microsoft Visual C++ 6.0
?
【需求分析】
對(duì)于給定
n
種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價(jià)值最大化。
?
【設(shè)計(jì)原理】
一、回溯法：
回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過(guò)對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來(lái)求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。
二、算法框架：
1
、問題的解空間：應(yīng)用回溯法解問題時(shí)，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)到少包含問題的一個(gè)（最優(yōu)）解。
2
、回溯法的基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。換句話說(shuō)，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。
運(yùn)用回溯法解題通常包含以下三個(gè)步驟：
（
1
）針對(duì)所給問題，定義問題的解空間；
（
2
）確定易于搜索的解空間結(jié)構(gòu)；
（
3
）以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索；
3
、遞歸回溯：由于回溯法是對(duì)解空間的深度優(yōu)先搜索，因此在一般情況下可用遞歸函數(shù)來(lái)實(shí)現(xiàn)回溯法。
【概要設(shè)計(jì)】
0
—
1
背包問題是一個(gè)子集選取問題，適合于用子集樹表示
0
—
1
背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。
int c;//
背包容量
? int n; //
物品數(shù)
? int *w;//
物品重量數(shù)組
? int *p;//
物品價(jià)值數(shù)組
? int cw;//
當(dāng)前重量
? int cp;//
當(dāng)前價(jià)值
? int bestp;//
當(dāng)前最優(yōu)值
? int *bestx;//
當(dāng)前最優(yōu)解
? int *x;//
當(dāng)前解
?
int Knap::Bound(int i)//
計(jì)算上界
void Knap::Backtrack(int i)//
回溯
?
int Knapsack(int p[],int w[],int c,int n) //
為
Knap::Backtrack
初始化
?
【詳細(xì)設(shè)計(jì)】
#include<iostream>
using namespace std;
?
?
?
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
?
public:
?????? void print()
?????? {
??????
?for(int m=1;m<=n;m++)
?? {
??? cout<<bestx[m]<<" ";
?? }
?? cout<<endl;
?????? };
?
private:
? int Bound(int i);
? void Backtrack(int i);
?
? int c;//
背包容量
? int n; //
物品數(shù)
? int *w;//
物品重量數(shù)組
? int *p;//
物品價(jià)值數(shù)組
? int cw;//
當(dāng)前重量
? int cp;//
當(dāng)前價(jià)值
? int bestp;//
當(dāng)前最優(yōu)值
? int *bestx;//
當(dāng)前最優(yōu)解
? int *x;//
當(dāng)前解
?
};
?
?
int Knap::Bound(int i)
{
?//
計(jì)算上界
?????? int cleft=c-cw;//
剩余容量
?????? int b=cp;
?????? //
以物品單位重量?jī)r(jià)值遞減序裝入物品
?????? while(i<=n&&w[i]<=cleft)
?????? {
??????
? cleft-=w[i];
??????
? b+=p[i];
??????
? i++;
?????? }
?????? //
裝滿背包
?????? if(i<=n)
????????????? b+=p[i]/w[i]*cleft;
?????? return b;
}
?
?
void Knap::Backtrack(int i)
{
? if(i>n)
? {
??? if(bestp<cp)
?????? {
???
?????? for(int j=1;j<=n;j++)
??????
???
??????
?bestx[j]=x[j];
??????
??? bestp=cp;
?????? }
?????? return;
? }
? if(cw+w[i]<=c) //
搜索左子樹
? {????????????
????? x[i]=1;
??????
? cw+=w[i];
??????
? cp+=p[i];
??????
? Backtrack(i+1);
??????
? cw-=w[i];
??????
? cp-=p[i];
? }
??????
? if(Bound(i+1)>bestp)//
搜索右子樹
??????
? {
??????
????? x[i]=0;
?????????????
? Backtrack(i+1);
??????
? }
?
}
?
?
class Object
{
?friend int Knapsack(int p[],int w[],int c,int n);
public:
?????? int operator<=(Object a)const
?????? {
??????
?return (d>=a.d);
?????? }
private:
?????? int ID;
?????? float d;
};
?
?
int Knapsack(int p[],int w[],int c,int n)
{
?//
為
Knap::Backtrack
初始化
?????? int W=0;
?????? int P=0;
?????? int i=1;
?????? Object *Q=new Object[n];
?????? for(i=1;i<=n;i++)
?????? {
??????
?Q[i-1].ID=i;
??????
?Q[i-1].d=1.0*p[i]/w[i];
??????
?P+=p[i];
??????
?W+=w[i];
?????? }
?????? if(W<=c)
????????????? return P;//
裝入所有物品
?????? //
依物品單位重量排序
?????? float f;
?????? for( i=0;i<n;i++)
??????
?for(int j=i;j<n;j++)
??????
?{
??????
? if(Q[i].d<Q[j].d)
??????
? {
??????
??? f=Q[i].d;
????????????? Q[i].d=Q[j].d;
????????????? Q[j].d=f;
??????
? }
?
?
??????
?}
??????
?????? Knap? K;
?????? K.p = new int[n+1];
??? K.w = new int[n+1];
?????? K.x = new int[n+1];
?????? K.bestx = new int[n+1];
?????? K.x[0]=0;
?????? K.bestx[0]=0;
?????? for( i=1;i<=n;i++)
?????? {
??????
?K.p[i]=p[Q[i-1].ID];
??????
?K.w[i]=w[Q[i-1].ID];
?????? }
?????? K.cp=0;
?????? K.cw=0;
?????? K.c=c;
?????? K.n=n;
?????? K.bestp=0;
?????? //
回溯搜索
?????? K.Backtrack(1);
??? K.print();
??? delete [] Q;
?????? delete [] K.w;
?????? delete [] K.p;
?????? return K.bestp;
}
?
void main()
{
?????? int *p;
?????? int *w;
??? int c=0;
?????? int n=0;
?????? int i=0;
?
?????? cout<<"
請(qǐng)輸入背包個(gè)數(shù)：
"<<endl;
??? cin>>n;
?????? p=new int[n+1];
?????? w=new int[n+1];
?????? p[0]=0;
?????? w[0]=0;
?
?????? cout<<"
請(qǐng)輸入個(gè)背包的價(jià)值：
"<<endl;
?????? for(i=1;i<=n;i++)
????????????? cin>>p[i];
?
?????? cout<<"
請(qǐng)輸入個(gè)背包的重量：
"<<endl;
?????? for(i=1;i<=n;i++)
????????????? cin>>w[i];
?
?????? cout<<"
請(qǐng)輸入背包容量：
"<<endl;
?????? cin>>c;
?
?????? cout<<Knapsack(p,w,c,n)<<endl;
?
??????
}