编辑代码

#include<iostream>
using namespace std;
#define MAXN 20
int n=5;   //物品数量
int W=10;   //最大重量
int w[]={0,6,5,4,2,1};  //存放物品重量，下标为0元素不用 
int v[]={0,5,3,5,3,2};  //存放物品价值，下标为0元素不用 
int x[MAXN];//最终解
int maxv; //最优解
void dfs(int i,int tw,int tv,int op[]) //tw:表示装入背包中的的物品总重量,tv:表示背包中物品总价值,op:记录一个解向量
{
	if(i>n)
	{
		if(tw==W&&tv>maxv)
		{
			maxv=tv;
			for(int j=1;j<=n;j++)
			x[j]=op[j];
		 } 
	 }
	 else
	 {
	 	op[i]=1;
		 dfs(i+1,tw+w[i],tv+v[i],op);
		 op[i]=0;
		 dfs(i+1,tw,tv,op); 
	 }	 
}

void dispsolution()
{
	int i;
	for(i=1;i<=n;i++)
	if(x[i]==1)
	cout<<"选取第"<<i<<"个物品"<<endl;
	cout<<"总价值 = "<<maxv;
 } 

 int main(){
 	int op[MAXN];
 	dfs(1,0,0,op);
 	dispsolution();
 	return 0;
 }