程序填空题：0/1背包问题（分支限界法）

0/1背包问题。给定一载重量为m的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求把物体装入背包，使背包的物体价值最大。

### 输入格式:

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

### 输出格式:

第一行输出输出所求X[n]数组，第二行输出装入背包内的物体的最大价值。

### 输入样例1:

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

### 输出样例1:

```out
11001
15
```
### 输入样例2:

```in
5 10
11 2
13 10
12 5
13 3
11 6
```

### 输出样例2:

```out
00
0
```


```c++
#include 
#include 
#include 
using namespace std;
#define MAXN 20						//最多可能物品数
//问题表示
int n,W;
int w[MAXN+1];				//重量，下标0不用
int v[MAXN+1];  				//价值，下标0不用
//求解结果表示
int maxv=-9999;						//存放最大价值,初始为最小值
int bestx[MAXN+1];					//存放最优解,全局变量
int total=1;						//解空间中结点数累计,全局变量
struct NodeType						//队列中的结点类型
{	int no;							//结点编号
	int i;							//当前结点在搜索空间中的层次
	int w;							//当前结点的总重量
	int v;							//当前结点的总价值
	int x[MAXN+1];					//当前结点包含的解向量
	double ub;						//上界
};

void bound(NodeType &e)			//计算分枝结点e的上界
{
	int i=e.i+1;
	int sumw=e.w;
	double sumv=e.v;
	while ()
	{	sumw+=w[i];				//计算背包已装入载重
		sumv+=v[i];				//计算背包已装入价值
		i++;
	}
	if (i<=n)	
		e.ub=;
	else
		e.ub=sumv;
}

void EnQueue(NodeType e,queue &qu)	//结点e进队qu
{
	if (e.i==n)					//到达叶子结点
	{
		if (e.v>maxv)			//找到更大价值的解
		{
			;
			for (int j=1;j<=n;j++)
				;
		}
	}
	else qu.push(e);			//非叶子结点进队
}
void bfs()							//求0/1背包的最优解
{
	int j;
	NodeType e,e1,e2;				//定义3个结点
	queue qu;				//定义一个队列
	e.i=0;							//根结点置初值，其层次计为0
	e.w=0; e.v=0;
	e.no=total++; 
	for (j=1;j<=n;j++)
		e.x[j]=0;
	bound(e);						//求根结点的上界
	qu.push(e);						//根结点进队
	while (!qu.empty())				//队不空循环
	{
		e=qu.front(); qu.pop();		//出队结点e
		e1.no=total++; 
		e1.i=e.i+1;				//建立左孩子结点
		e1.w=e.w+w[e1.i];
		e1.v=e.v+v[e1.i];
		for (j=1;j<=n;j++)		//复制解向量
			e1.x[j]=e.x[j];
		e1.x[e1.i]=1;
		bound(e1);				//求左孩子结点的上界		
		if  ()		//剪枝：检查左孩子结点
		{
			EnQueue(e1,qu);			//左孩子结点进队操作
		}
		e2.no=total++;				//建立右孩子结点
		e2.i=e.i+1;
		e2.w=; 
		e2.v=;
		for (j=1;j<=n;j++)			//复制解向量
			e2.x[j]=e.x[j];
		e2.x[e2.i]=;
		bound(e2);					//求右孩子结点的上界
		if ()				//若右孩子结点可行,则进队,否则被剪枝
			EnQueue(e2,qu);
	}
}
int main()
{
	cin>>n>>W; //输入物体个数及背包载重量 
	for(int i=1;i<=n;i++)//输入各物体重量及价值 
		cin>>w[i]>>v[i];	
	bfs();					//调用队列式分枝限界法求0/1背包问题

	for(int i=1;i<=n;i++)
		printf("%d",bestx[i]);
	printf("\n%d",maxv);
	return 0;
}
```






答案：
第1空：(sumw+w[i]<=W) && i<=n    

第2空：sumv+(W-sumw)*v[i]/w[i]    

第3空：maxv=e.v    

第4空：bestx[j]=e.x[j]    

第5空：e.w+w[e.i+1]<=W&&e1.ub>maxv    

第6空：e.w    

第7空：e.v    

第8空：0    

第9空：e2.ub>maxv