算法设计例题：装载问题（回溯、分枝限界）
memory limit: 5000KB time limit: 500MS
accept: 12 submit: 29
Description
有一批概共n个集装箱要装上两艘载重量分别为c1和c2的轮船，其中，集装箱i的重量为wi，且 
。
装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船。
Input
输入的第一个为测试样例的个数T（ T < 120 ），接下来有T个测试样例。每个测试样例的第一行是集装箱个数n（ n <= 20 ），第二行是两个整数c1和c2，表示两艘轮船的载重量，接下来n行，每行一个整数wi，表示第i个集装箱的重量，（ 0 ，i = 1, 2, …, n，0 < c1, c2 < 30000 ）
Output
对应每个测试样例输出两行，第一行格式为"Case #:"，其中'#'表示第几个测试样例（从1开始计）。
第二行格式为：如果找不到合理的装载方案，则输出"No"，否则输出最优载重量。
Sample Input
2
3
50 50
10 40 40
3
50 50
20 40 40
Sample Output
Case 1:
50
Case 2:
No
Hint
容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：
（1） 首先将第一艘轮船尽可能装满；
（2） 将剩余的集装箱装上第二艘轮船。
========================================
#include"iostream"
#include"stdlib.h"
#include <string.h>
/*
2
3
50 50
20 10 30
3
50 50
10 40 30
*/
using namespace std ;
class Loading {
public :
int n ;//集装箱数
int w[40] ;//集装箱重量数组
int c ;//第一搜轮船的载重量
int cw;//当前载重量
int bestw;//当前最优载重量
int r;//剩余集装箱重量
public :
int maxLoading( )
{
cw = 0 ;
bestw = 0;
//初始化r
backtrack(1);
//计算最优解
return bestw;
}
void backtrack(int i )
{
int j;
//搜索第i层结点
if(i>n)
//到达叶子结点
{
if(cw>bestw)
bestw = cw ;
return;
}
//
//搜索子树
//！！！
r -=w[i];
if(cw+w[i]<=c)
{
//搜索左子树
cw+=w[i];
backtrack(i+1);
cw-=w[i];
}
if(cw+r>bestw)
{
backtrack(i+1);
}
r+=w[i];
}
};
int main()
{
Loading load ;
int T ;
int j =1 ;
cin>>T ;
int c1 ;
while(T>0)
{
cin>>load.n;
cin>>load.c;
cin>>c1;
int i =1 ;
int sum = 0;
load.r =0 ;
while(i<=load.n)
{
cin>>load.w[i];
load.r=load.r+load.w[i];
// cout<<"第"<<i<<"个集装箱"<<load.w[i]<<endl;
sum+=load.w[i];
i++;
}
// cout<<"sum:"<<sum<<endl;
load.maxLoading();
if(load.bestw>0&& ((sum-load.bestw)<=c1))
{
cout<<"Case "<<j<<":"<<endl;
cout<<load.bestw<<endl;
}else if(sum<=c1){
cout<<"Case "<<j<<":"<<endl;
cout<<load.bestw<<endl;
}else{
cout<<"Case "<<j<<":"<<endl;
cout<<"No"<<endl;
}
load.bestw = 0 ;
load.c = 0;
load.cw = 0;
load.n = 0 ;
load.r = 0 ;
int b =1 ;
for( ; b <40 ; b ++)
load.w[b]=0;
T--;
j++;
}
return 0 ;
}