題目
[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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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;
}
/**************************************************************
Problem: 1462
User: wangzhengyi
Language: C
Result: Accepted
Time:20 ms
Memory:11344 kb
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
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;
}
/**************************************************************
Problem: 1462
User: wangzhengyi
Language: C
Result: Accepted
Time:20 ms
Memory:11344 kb
****************************************************************/
