程序填空题：0/1背包问题（回溯法）

0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求而且重量和恰好为W具有最大的价值。

```c++
#include 
#include 
#include 
#define MAXN 20				//最多物品数
using namespace std;
int n;						//物品数
int W;						//限制重量
int w[MAXN]={0};			//存放物品重量,不用下标0元素
int v[MAXN]={0};			//存放物品价值,不用下标0元素
int x[MAXN];					//存放最终解
int maxv; 						//存放最优解的总价值
void dfs(int i,int tw,int tv,int rw,int op[]) //求解0/1背包问题
{
	int j;
	if (i>n)					//找到一个叶子结点
	{	if () 	//找到一个满足条件的更优解,保存它
		{	maxv=tv;
			for ()	//复制最优解
				x[j]=op[j];
		}
	}
	else						//尚未找完所有物品
	{	if ()  		//左孩子结点剪枝：满足条件时才放入第i个物品
		{
			op[i]=1;			//选取第i个物品
			dfs();
		}
		op[i]=0;				//不选取第i个物品,回溯
		if ()			//右孩子结点剪枝
			dfs();
	}
}
void dispasolution()			//输出最优解
{	int i;
	for (i=1;i<=n;i++)
		if (x[i]==1)
			printf("%d ",i);
	printf("\n%d %d",W,maxv);
}
int main()
{
	int i;
	cin>>n>>W; //输入物体个数及背包载重量 
	for(int i=1;i<=n;i++)//输入各物体重量及价值 
		cin>>w[i]>>v[i];
	int op[MAXN];				//存放临时解
	memset(op,0,sizeof(op));
	int rw=0;
	for (int i=1;i<=n;i++)
		rw+=w[i];
	dfs(1,0,0,rw,op);
	dispasolution();
	return 0;
}

```

### 输入格式:

第一行输入背包载重量W及背包个数n，再依次输入n行，每行为背包重量wi和价值vi。

### 输出格式:

第一行输出输出装入背包内的物体编号(末尾有空格)，第二行输出背包内的物体总重量和总价值。

### 输入样例1:

```in
5 10
2 6
2 3
6 5
5 4
4 6
```

### 输出样例1:

```out
1 2 3 
10 14 
```





答案：
第1空：tw==W && tv>maxv    

第2空：j=1;j<=n;j++    

第3空：tw+w[i]<=W    

第4空：i+1,tw+w[i],tv+v[i],rw-w[i],op    

第5空：tw+rw>W    

第6空：i+1,tw,tv,rw-w[i],op