【實驗目的】
學習掌握回溯算法。
?
【實驗內容】
用回溯法求解
0
—
1
背包問題，并輸出問題的最優解。
0
—
1
背包問題描述如下：
給定
n
種物品和一背包。物品
i
的重量是
Wi
，其價值為
Vi
，背包的容量是
c
，問應如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大。
?
【實驗條件】
Microsoft Visual C++ 6.0
?
【需求分析】
對于給定
n
種物品和一背包。在容量最大值固定的情況下，要求裝入的物品價值最大化。
?
【設計原理】
一、回溯法：
回溯法是一個既帶有系統性又帶有跳躍性的的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。
二、算法框架：
1
、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
2
、回溯法的基本思想：確定了解空間的組織結構后，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，并成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，并使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（
1
）針對所給問題，定義問題的解空間；
（
2
）確定易于搜索的解空間結構；
（
3
）以深度優先的方式搜索解空間，并且在搜索過程中用剪枝函數避免無效搜索；
3
、遞歸回溯：由于回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法。
【概要設計】
0
—
1
背包問題是一個子集選取問題，適合于用子集樹表示
0
—
1
背包問題的解空間。在搜索解空間樹是，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。
int c;//
背包容量
? int n; //
物品數
? int *w;//
物品重量數組
? int *p;//
物品價值數組
? int cw;//
當前重量
? int cp;//
當前價值
? int bestp;//
當前最優值
? int *bestx;//
當前最優解
? int *x;//
當前解
?
int Knap::Bound(int i)//
計算上界
void Knap::Backtrack(int i)//
回溯
?
int Knapsack(int p[],int w[],int c,int n) //
為
Knap::Backtrack
初始化
?
【詳細設計】
#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; //
物品數
? int *w;//
物品重量數組
? int *p;//
物品價值數組
? int cw;//
當前重量
? int cp;//
當前價值
? int bestp;//
當前最優值
? int *bestx;//
當前最優解
? int *x;//
當前解
?
};
?
?
int Knap::Bound(int i)
{
?//
計算上界
?????? int cleft=c-cw;//
剩余容量
?????? int b=cp;
?????? //
以物品單位重量價值遞減序裝入物品
?????? 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<<"
請輸入背包個數：
"<<endl;
??? cin>>n;
?????? p=new int[n+1];
?????? w=new int[n+1];
?????? p[0]=0;
?????? w[0]=0;
?
?????? cout<<"
請輸入個背包的價值：
"<<endl;
?????? for(i=1;i<=n;i++)
????????????? cin>>p[i];
?
?????? cout<<"
請輸入個背包的重量：
"<<endl;
?????? for(i=1;i<=n;i++)
????????????? cin>>w[i];
?
?????? cout<<"
請輸入背包容量：
"<<endl;
?????? cin>>c;
?
?????? cout<<Knapsack(p,w,c,n)<<endl;
?
??????
}