原题地址
http://ac.jobdu.com/problem.php?pid=1462
附上启发我的大神作品
原题:
http://acm.hdu.edu.cn/showproblem.php?pid=1864
解析:
http://www.cnblogs.com/aiyite826/archive/2010/07/23/1783859.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
/*
*这次组织的考试算是被狂虐了,这题本来真是该会的,只是由于一直纠结于双塔问题,导致思路不通
*/
#include <stdio.h>
#include <string.h>
int list[101];
int dp[5001];
int main(){
int n, c1, c2, sum, i;
while(~scanf("%d%d%d", &n, &c1, &c2)){
sum = 0;
for(i = 1; i <= n; i++){
scanf("%d", &list[i]);
sum += list[i];
}
memset(dp, 0, sizeof(dp));//初始化dp = 0
for(i = 1; i <= n; i++)
for(int j = c1; j >= list[i]; j--)
dp[j] = dp[j] >= dp[j - list[i]] + list[i] ? dp[j] : dp[j - list[i]] + list[i];
//寻找在装在j,前i块重物中能容纳的最大,此处有点不容易理解
puts(dp[c1] + c2 >= sum ? "YES" : "NO");
}
return 0;
}