题目
[html]
题目描述：
给定n个物品的重量和两艘载重量分别为c1和c2的船，问能否用这两艘船装下所有的物品。
输入：
输入包含多组测试数据，每组测试数据由若干行数据组成。
第一行为三个整数，n c1 c2，（1 <= n <= 100）,(1<=c1,c2<=5000)。
接下去n行，每行一个整数，代表每个物品的重量(重量大小不大于100)。
输出：
对于每组测试数据，若只使用这两艘船可以装下所有的物品，输出YES。
否则输出NO。
样例输入：
3 5 8
6
3
3
3 5 8
5
3
4
样例输出：
NO
YES
题目描述：
给定n个物品的重量和两艘载重量分别为c1和c2的船，问能否用这两艘船装下所有的物品。
输入：
输入包含多组测试数据，每组测试数据由若干行数据组成。
第一行为三个整数，n c1 c2，（1 <= n <= 100）,(1<=c1,c2<=5000)。
接下去n行，每行一个整数，代表每个物品的重量(重量大小不大于100)。
输出：
对于每组测试数据，若只使用这两艘船可以装下所有的物品，输出YES。
否则输出NO。
样例输入：
3 5 8
6
3
3
3 5 8
5
3
4
样例输出：
NO
YES
思路
最初思路（错误）
开始考虑是贪心算法，每次找一个最重的货物，还写了个测试代码：
[cpp]
#include
#include
int cmp_data(const void *p, const void *q)
{
const int *a = p;
const int *b = q;
return *b - *a;
}
int main(void)
{
int i, n, c1, c2, *arr;
while (scanf("%d", &n) != EOF) {
scanf("%d %d", &c1, &c2);
arr = (int *)malloc(sizeof(int) * n);
for (i = 0; i < n; i ++)
scanf("%d", &arr[i]);
qsort(arr, n, sizeof(arr[0]), cmp_data);
// 贪心算法
int flag;
for (i = 0, flag = 1; i < n; i ++) {
if (c1 >= arr[i]) {
c1 -= arr[i];
} else if (c2 >= arr[i]) {
c2 -= arr[i];
} else {
flag = 0;
break;
}
}
if (flag) {
printf("YES\n");
} else {
printf("NO\n");
}
free(arr);
}
return 0;
}
#include
#include
int cmp_data(const void *p, const void *q)
{
const int *a = p;
const int *b = q;
return *b - *a;
}
int main(void)
{
int i, n, c1, c2, *arr;
while (scanf("%d", &n) != EOF) {
scanf("%d %d", &c1, &c2);
arr = (int *)malloc(sizeof(int) * n);
for (i = 0; i < n; i ++)
scanf("%d", &arr[i]);
qsort(arr, n, sizeof(arr[0]), cmp_data);
// 贪心算法
int flag;
for (i = 0, flag = 1; i < n; i ++) {
if (c1 >= arr[i]) {
c1 -= arr[i];
} else if (c2 >= arr[i]) {
c2 -= arr[i];
} else {
flag = 0;
break;
}
}
if (flag) {
printf("YES\n");
} else {
printf("NO\n");
}
free(arr);
}
return 0;
}
但是很明显这种做法是错误的，理由就是举出一个反例：3 5 8 5 4 4
正确的思路
其实不用考虑两条船的问题，就考虑一条船最多能带多少货物，假设最多带为w,然后看看总共重量sum - w是否小于第二条船的载重量即可，是个0-1背包问题
AC代码
[cpp]
#include
#include
int cmp_data(const void *p, const void *q)
{
const int *a = p;
const int *b = q;
return *a - *b;
}
int main(void)
{
int i, j, n, c1, c2, sum, *arr, **dp;
while (scanf("%d", &n) != EOF) {
scanf("%d %d", &c1, &c2);
arr = (int *)malloc(sizeof(int) * (n + 1));
arr[0] = 0;
for (i = 1, sum = 0; i <= n; i ++) {
scanf("%d", &arr[i]);
sum += arr[i];
}
qsort(arr, n, sizeof(arr[0]), cmp_data);
// 0-1背包
dp = (int **)malloc(sizeof(int *) * (n + 1));
for (i = 0; i <= n; i ++)
dp[i] = (int *)malloc(sizeof(int) * (c1 + 1));
for (i = 0; i <= c1; i ++)
dp[0][i] = 0;
for (i = 0; i <= n; i ++)
dp[i][0] = 0;
for (i = 1; i <= n; i ++) {
for (j = 1; j <= c1; j ++) {
if (arr[i] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = (dp[i - 1][j] > arr[i] + dp[i - 1][j - arr[i]]) dp[i - 1][j] : arr[i] + dp[i - 1][j - arr[i]];
}
}
}
if (sum - dp[n][c1] <= c2) {
printf("YES\n");
} else {
printf("NO\n");
}
free(arr);
}
return 0;
}
/**********************************************************