/*描述:有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船,其中,集装箱i的重量为wi,且
集装箱重量总和小于等于两辆轮船的载重量总和。
装在问提要求确定是否存在一个方案可将这n个集装箱装上两艘轮船。
若有,找出一种装在方案。
解决方法:(1)首先将第一艘轮船极可能装满
(2)将其余的集装箱装载第二艘轮船
装载第一艘轮船的方法等价于一个特殊的0-1背包问题
*/
#include
using namespace std;
int c1[100], c2[100];//两艘轮船的载重量
int n[100];//集装箱个数
int w[1000];//每个集装箱的重量
int bestw = 0;//记录当前第一搜轮船装载的最大值
int a[1000];//记录每个集装箱是否被装进第一搜轮船
//插入排序
void InsertSort(int A[], int N)
{
int j, p;
int tmp;
for(p = 1; p < N; p++) {
tmp = A[p];
for(j = p; j > 0 && A[j - 1] > A[j]; j--) {
A[j] = A[j - 1];
}
A[j] = tmp;
}
}
void search(int m)
{
if(m >= n)//这里提示有问题
return;
else {
if(w[m] <= c1 - bestw)//这里提示有问题
{
a[m] = 1;
bestw = bestw + w[m];
}
else a[m] = 0;
search(m + 1);
}
}
//判断函数
bool outp(int c1, int C2, int N)
{
int i;
//对集装箱的重量进行插入排序
InsertSort(w, N);
//将将第一个集装箱尽可能装满
search(0);
int wz = 0;//集装箱总重量
for(i = 0; i < N; i++) {
wz = wz + w[i];
}
//做出判断
if(C2 >= wz - bestw)
return true;
else
return false;
}
int main()
{
int i = -1, j;
do {
i++;
cin >> c1[i] >> c2[i] >> n[i];//输入载重量和集装箱的个数
int i;//循环变量
for(j = 0; j < n[i]; j++) {
//输入每个集装箱的重量
cin >> w[i];
}
}while(c1[i] || c2[i] || n[i]);
int tmp = i;
for(i = 0; i < tmp; i++) {
if(outp(c1[i], c2[i], n[i]))
cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
编译提示
error: ISO C++ forbids comparison between pointer and integer