`
coolsooner
  • 浏览: 1303006 次
文章分类
社区版块
存档分类
最新评论

装载问题(西农Oj) 解题报告

 
阅读更多

描述:

有两艘船,载重量分别是c1、 c2,n个集装箱,重量是wi (i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。

输入:

多个测例,每个测例的输入占两行。第一行一次是c1、c2和n(n<=10);第二行n个整数表示wi (i=1…n)。n等于0标志输入结束。

输出:

对于每个测例在单独的一行内输出Yes或No。

输入样例:

7 8 2
8 7
7 9 2
8 8
0 0 0

输出样例:

Yes
No

解题思路:要使之能够多的装载集装箱,应使得每装集装箱的,和船的容量比一下,和哪个船的差值大的就装入这个集装箱里,保证能够有更多的空间装箱子。

代码如下:

Code:
  1. #include<iostream>
  2. usingnamespacestd;
  3. intmain()
  4. {
  5. intc1,c2,n;
  6. while(1)
  7. {
  8. intstate=0;
  9. cin>>c1>>c2>>n;
  10. if(c1==0&&c2==0&&n==0)
  11. return0;
  12. while(n)
  13. {
  14. intwi;
  15. cin>>wi;
  16. if(wi<=c1||wi<=c2)
  17. {
  18. if(wi>c1)
  19. c2=c2-wi;
  20. elseif(wi>c2)
  21. c1=c1-wi;
  22. else
  23. {
  24. if(c1-wi>c2-wi)
  25. c1=c1-wi;
  26. else
  27. c2=c2-wi;
  28. }
  29. if(c1<0||c2<0)
  30. {
  31. cout<<"No"<<endl;
  32. intstate=1;
  33. break;
  34. }
  35. }
  36. else
  37. {
  38. cout<<"No"<<endl;
  39. state=1;
  40. break;
  41. }
  42. n--;
  43. }
  44. if(c1<0||c2<0)
  45. cout<<"No"<<endl;
  46. if(state==0)
  47. cout<<"Yes"<<endl;
  48. }
  49. return0;
  50. }

当然也可以用这种思想去做:求出不超过c1的最大值max,若总重量-max < c2则能装入到两艘船。

在求max的时候用到回溯法,物品只有两种状态,那么放进去要么没放在这个集装箱里。

代码如下:

Code:
  1. #include<iostream>
  2. usingnamespacestd;
  3. constintmax(12);
  4. intc1,c2,n;
  5. intweight;
  6. intbest;
  7. intboxw[max];
  8. voidbacktrack(inta)
  9. {
  10. if(a==n)
  11. {
  12. if(weight>best)
  13. best=weight;
  14. return;
  15. }
  16. if(weight+boxw[a]<=c1)
  17. {
  18. weight=weight+boxw[a];
  19. backtrack(a+1);
  20. weight=weight-boxw[a];
  21. }
  22. backtrack(a+1);
  23. }
  24. intmain()
  25. {
  26. while(1)
  27. {
  28. intsum=0;
  29. cin>>c1>>c2>>n;
  30. if(c1==0&&c2==0&&n==0)
  31. break;
  32. for(inti=0;i<n;i++)
  33. {
  34. cin>>boxw[i];
  35. sum+=boxw[i];
  36. }
  37. best=weight=0;
  38. backtrack(0);
  39. if(sum-best<=c2)
  40. cout<<"Yes"<<endl;
  41. else
  42. cout<<"No"<<endl;
  43. }
  44. return0;
  45. }

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics