最新消息:热烈庆祝IT小记上线!

题目1462:两船载物问题

题目描述:

给定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 <iostream>
#include <cstdio>  
#include <cstring>
using namespace std;

int dp[5003];
int a[103];

int max(int a,int b){
	return a > b ? a: b;
}
int main()  
{  
	int n,c1,c2,sum;
	while(cin >> n >> c1 >> c2){
		sum = 0;
		for(int i = 0;i < n; i++){
			scanf("%d",&a[i]);
			sum += a[i];
		}
		memset(dp,0,sizeof(dp));
		for(int i = 0;i < n;i++)
			for(int j = c1;j >= a[i]; j--){
				dp[j] = max(dp[j],dp[j - a[i]] + a[i]);
			}
       if(sum - dp[c1] > c2)
		   cout << "NO" << endl;
	   else
		   cout << "YES" << endl;
	}
	return 0;  
}  


上一篇

猜您喜欢

备案号:苏ICP备12016861号-4