Jobdu 1462：两船载物问题 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

九度笔记之 1462：两船载物问题 - KingEasternSun的专栏 - 博客频道 - CSDN.NET

给定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

在一条船上尽可能多的放置货物，然后看剩下的货物另外一条船能否装下。

dp[j]表示容量为j的船只 所能装的最多的货物量，每次考虑一个货物，更新dp[j]

1. for(int j = smallBoat; j>=boatw[i]; j--){  
2.     dp[j] = std::max(dp[j],boatw[i]+dp[j-boatw[i]]); 

注意更新dp[j]一定是从高到低更新。原因可参考题目1209：最小邮票数

1. for(int j = smallBoat; j>=boatw[i]; j--){  
2.     booldp[j] = booldp[j] || booldp[j-boatw[i]];  
3. }  

1. void init(int n){  
2.     sumw  = 0;  
3.     for(int i = 1;i<n+1;i++){  
4.         scanf("%d",boatw+i);  
5.         sumw+=boatw[i];  
6.     }  
7.    
8. }  
9. void judge(int n,int smallBoat,int bigBoat){  
10.    
11.     if(sumw > smallBoat+bigBoat){  
12.         printf("NO\n");  
13.         return;  
14.     }  
15.     // *dp = new int[boat1 + 1];  
16.     memset(dp,0,(smallBoat+1)*sizeof(int));  
17.     for(int i = 1;i<n+1;i++){  
18.         for(int j = smallBoat; j>=boatw[i]; j--){  
19.             dp[j] = std::max(dp[j],boatw[i]+dp[j-boatw[i]]);  
20.         }  
21.     }  
22.    
23.     if(sumw - dp[smallBoat] <=bigBoat ){  
24.         printf("YES\n");  
25.     }else  
26.         printf("NO\n");  
27.    
28. }  

也就是 在给定船只大小smallboat，和货物重量的情况下，哪些实际装载量可以实现。

booldp[j] 为真表示可以实现j个装载量，更新过程如下

1. for(int j = smallBoat; j>=boatw[i]; j--){  
2.     booldp[j] = booldp[j] || booldp[j-boatw[i]];  
3. }  

需要注意的是 booldp[0] 一定要设置为true，因为在船上一个货物都不放，就是0，booldp[0]=true.

算法的时间复杂度与smallboat有关，所以如果两只船只重量相差很大的话，对小船求最大载重可以减少程序时间。

1. void judgenew(int n,int smallBoat,int bigBoat){//using bool  
2.    
3.     if(sumw > smallBoat+bigBoat){  
4.         printf("NO\n");  
5.         return;  
6.     }  
7.     bool *booldp = new bool[smallBoat + 1];  
8.     memset(booldp,0,(smallBoat+1)*sizeof(bool));  
9.     booldp[0] = true;//Attention  must be true  
10.    
11.     for(int i = 1;i<n+1;i++){  
12.         for(int j = smallBoat; j>=boatw[i]; j--){  
13.             booldp[j] = booldp[j] || booldp[j-boatw[i]];  
14.         }  
15.     }  
16.    
17.     for(int i = smallBoat;i>=0;i--){  
18.         if(booldp[i]){  
19.             if(sumw - i<=bigBoat)  
20.                 printf("YES\n");  
21.             else  
22.                 printf("NO\n");  
23.             return;  
24.         }  
25.     }  
26. }  

http://www.xuebuyuan.com/1537195.html

 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");
 }

Read full article from 九度笔记之 1462：两船载物问题 - KingEasternSun的专栏 - 博客频道 - CSDN.NET