程序填空题：求解简单装载问题（回溯法）

有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1≤i≤n）的重量为wi。不考虑集装箱的体积限制，现要这些集装箱中选出若干装上轮船，使它们的重量之和等于W，当总重量相同时要求选取的集装箱个数尽可能少。

```c++
#include
#include
#include
using namespace std;
#define MAXN 20 //最多集装箱个数
//问题表示
int w[MAXN]={0}; //各集装箱重量,不用下标0的元素
int n,W;
int maxw; //存放最优解的总重量
int x[MAXN]; //存放最优解向量
int minnum=999999; //存放最优解的集装箱个数,初值为最大值

void dfs(int num,int tw,int rw,int op[],int i) //考虑第i个集装箱
{
if (i>n) //找到一个叶子结点
{
if (tw==W && num { ; //找到一个满足条件的更优解
minnum=num;
for (int j=1;j<=n;j++)
;
}
}
else //尚未找完所有集装箱
{ op[i]=1; //选取第i个集装箱
if (tw+w[i]<=W) //左孩子结点剪枝：装载满足条件的集装箱
dfs();
op[i]=0; //不选取第i个集装箱,回溯
if (tw+rw>W) //右孩子结点剪枝
dfs();
}
}

void dispasolution(int n) //输出一个解
{
for (int i=1;i<=n;i++)
if (x[i]==1)
printf("%d ",i);
}
int main()
{
int i;
cin>>n>>W;
for(int i=1;i<=n;i++)
cin>>w[i];
int op[MAXN]; //存放临时解
memset(op,0,sizeof(op));
int rw=0;
for (int i=1;i<=n;i++)
rw+=w[i];
dfs();
dispasolution(n);
return 0;
}

```

### 输入格式:

第一行输入集装箱个数n和载重量W，第二行依次输入n个集装箱的重量wi。

### 输出格式:

输出选取的集装箱编号（按输入顺序从1开始依次编号）。

### 输入样例1:

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

### 输出样例1:

```out
3 4
```





答案：
第1空：maxw=tw

第2空：x[j]=op[j]

第3空：num+1,tw+w[i],rw-w[i],op,i+1

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

第5空：0,0,rw,op,1