两船载物问题
題目1462：兩船載物問題
時間限制：1 秒
內存限制：128 兆
特殊判題：否
提交：690
解決：167
題目描述： 給定n個物品的重量和兩艘載重量分別為c1和c2的船，問能否用這兩艘船裝下所有的物品。
輸入包含多組測試數(shù)據(jù)，每組測試數(shù)據(jù)由若干行數(shù)據(jù)組成。
第一行為三個整數(shù)，n c1 c2，（1 <= n <= 100）,(1<=c1,c2<=5000)。
接下去n行，每行一個整數(shù)，代表每個物品的重量(重量大小不大于100)。
對于每組測試數(shù)據(jù)，若只使用這兩艘船可以裝下所有的物品，輸出YES。
否則輸出NO。
YES
問題是看兩個船能不能把所有物品運走，可以分析為一個船運走的最大物體重量，剩下的查看重量是不是超過另一個船的運力。就是在一條船上盡可能多的放置貨物，然后看剩下的貨物另外一條船能否裝下。
#include <iostream> #include <stdio.h> #include <cstring> using namespace std; //::vector<int> wts; int boatw[101]={0}; int dp[5001]={0}; int sumw = 0;void init(int n){sumw = 0;for(int i = 1;i<n+1;i++){scanf("%d",boatw+i);sumw+=boatw[i];}} void judge(int n,int smallBoat,int bigBoat){if(sumw > smallBoat+bigBoat){printf("NO\n");return;}// *dp = new int[boat1 + 1];memset(dp,0,(smallBoat+1)*sizeof(int));for(int i = 1;i<n+1;i++){for(int j = smallBoat; j>=boatw[i]; j--){dp[j] = std::max(dp[j],boatw[i]+dp[j-boatw[i]]);}}if(sumw - dp[smallBoat] <=bigBoat ){printf("YES\n");}elseprintf("NO\n");} void judo(){int n;int boat1;int boat2;while(scanf("%d %d %d",&n,&boat1,&boat2)!=EOF){init(n);if(boat1<boat2)judgenew(n,boat1,boat2);elsejudgenew(n,boat2,boat1);} } int main() {judo();return 0; }
總結
- 上一篇： 最小邮票数
- 下一篇： Jobdu MM分水果