7-27 装载问题 (10 分)
有一批共n (n<100) 个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。
输入格式:
第一行输入三个数n，c1，c2(<=10^7)；第二行输入n个数，第i个数表示第i个集装箱的重量wi(<=10^5)。
输出格式:
如果能成功装载输出“YES”,否则输出“NO”
输入样例:
2 9 9 10 8
输出样例:
NO
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<stdio.h>
#define N 100
int c1,c2;
int n;
int w[N];
int flag[N]={0};
int r=0;
int cw=0;
int bw=0;
int choose[N];
void backtrack(int i){
int j;
if(i>n){
if(cw>bw){
bw=cw;
for(j=1;j<=n;j++){
choose[j]=flag[j];
}
}
return ;
}
r-=w[i];
if(cw+w[i]<=c1){
cw+=w[i];
flag[i]=1;
backtrack(i+1);
cw-=w[i];
flag[i]=0;
}
if(cw+r>bw){
backtrack(i+1);
}
r+=w[i];
}
int main()
{
int i,sum=0;
scanf("%d %d %d",&n,&c1,&c2);
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
r+=w[i];
sum+=w[i];
}
backtrack(1);
if(sum-bw<=c2){
printf("YES\n");
} else{
printf("NO\n");
}
}