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

有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且w1+w2+…+wn≤c1+c2。 装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这两艘轮船。如果有，找出一种装载方案。

```c++
#include
#include
#define MAXN 20 //最多集装箱个数
#include
using namespace std;
//问题表示
int w[MAXN]={0}; //各集装箱重量,不用下标0的元素
int n;
int c1,c2;
int maxw=0; //存放第一艘轮船最优解的总重量
int x[MAXN]; //存放第一艘轮船最优解向量

void dispasolution(int n) //输出一个解
{
for (int j=1;j<=n;j++)
if (x[j]==1)
printf("%d ",j);
cout< for (int j=1;j<=n;j++)
if (x[j]==0)
printf("%d ",j);

}

void dfs(int tw,int rw,int op[],int i) //求第一艘轮船的最优解
{
if (i>n) //找到一个叶子结点
{
if (tw>maxw)
{
; //找到一个满足条件的更优解,保存它
for (int j=1;j<=n;j++) //复制最优解
;
}
}
else //尚未找完所有集装箱
{ op[i]=1; //选取第i个集装箱
if (tw+w[i]<=c1) //左孩子结点剪枝：装载满足条件的集装箱
dfs();
op[i]=0; //不选取第i个集装箱,回溯
if (tw+rw>maxw) //右孩子结点剪枝
dfs();
}
}

bool solve() //求解复杂装载问题
{
int sum=0; //累计第一艘轮船装完后剩余的集装箱重量
for (int j=1;j<=n;j++)
if (x[j]==0)
sum+=w[j];
if (sum<=c2) //第二艘轮船可以装完
return true;
else //第二艘轮船不能装完
return false;
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>w[i];
cin>>c1>>c2;
int op[MAXN]; //存放临时解
memset(op,0,sizeof(op));
int rw=0;
for (int i=1;i<=n;i++)
rw+=w[i];
dfs(0,rw,op,1); //求第一艘轮船的最优解

if (solve()) //输出结果
{
dispasolution(n);
}
else
printf("No solution");
return 0;
}

```

### 输入格式:

第一行输入集装箱个数n，第二行依次输入n个集装箱的重量wi，第三行输入两艘载重量c1和c2。

### 输出格式:

第一行输出第一艘选取的集装箱编号，第二行输出第二艘选取的集装箱编号。（编号按输入顺序从1开始）
若没有合理的装载方案，输出“No solution”。

### 输入样例1:

```in
3
10 40 40
50 50
```

### 输出样例1:

```out
1 2
3
```





答案：
第1空：maxw=tw

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

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

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