学步园

问题：给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量是c，问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

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);
       }
}