描述:
有两艘船,载重量分别是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
解题思路:要使之能够多的装载集装箱,应使得每装集装箱的,和船的容量比一下,和哪个船的差值大的就装入这个集装箱里,保证能够有更多的空间装箱子。
代码如下:
-
#include<iostream>
-
usingnamespacestd;
-
intmain()
-
{
-
intc1,c2,n;
-
while(1)
-
{
-
intstate=0;
-
cin>>c1>>c2>>n;
-
if(c1==0&&c2==0&&n==0)
-
return0;
-
while(n)
-
{
-
intwi;
-
cin>>wi;
-
if(wi<=c1||wi<=c2)
-
{
-
-
if(wi>c1)
-
c2=c2-wi;
-
elseif(wi>c2)
-
c1=c1-wi;
-
else
-
{
-
if(c1-wi>c2-wi)
-
c1=c1-wi;
-
else
-
c2=c2-wi;
-
}
-
if(c1<0||c2<0)
-
{
-
cout<<"No"<<endl;
-
intstate=1;
-
break;
-
}
-
}
-
else
-
{
-
cout<<"No"<<endl;
-
state=1;
-
break;
-
}
-
n--;
-
}
-
if(c1<0||c2<0)
-
cout<<"No"<<endl;
-
if(state==0)
-
cout<<"Yes"<<endl;
-
}
-
return0;
- }
当然也可以用这种思想去做:求出不超过c1的最大值max,若总重量-max < c2则能装入到两艘船。
在求max的时候用到回溯法,物品只有两种状态,那么放进去要么没放在这个集装箱里。
代码如下:
-
#include<iostream>
-
usingnamespacestd;
-
constintmax(12);
-
intc1,c2,n;
-
intweight;
-
intbest;
-
intboxw[max];
-
voidbacktrack(inta)
-
{
-
if(a==n)
-
{
-
if(weight>best)
-
best=weight;
-
return;
-
}
-
if(weight+boxw[a]<=c1)
-
{
-
weight=weight+boxw[a];
-
backtrack(a+1);
-
weight=weight-boxw[a];
-
}
-
backtrack(a+1);
-
}
-
intmain()
-
{
-
while(1)
-
{
-
intsum=0;
-
cin>>c1>>c2>>n;
-
if(c1==0&&c2==0&&n==0)
-
break;
-
for(inti=0;i<n;i++)
-
{
-
cin>>boxw[i];
-
sum+=boxw[i];
-
}
-
best=weight=0;
-
backtrack(0);
-
if(sum-best<=c2)
-
cout<<"Yes"<<endl;
-
else
-
cout<<"No"<<endl;
-
}
-
return0;
- }
分享到:
相关推荐
这是杭电OJ上某些题的解题报告,后续还有上传很多!
若干百个,没细数,前几个下下来的有良心的回复一下帮我数数。
分类题解 ,几百个,chm document...............
南阳理工学院OJ第1版解题报告V1.0.pdf
包含很多ACM题目的源代码,各种类型都有,贪心,递归,分治,动态规划,RMQ,SPFA,BellmanDFSBFS
杭电oj1000题解题报告
杭州电子科技大学ACM教程PPT,刘春英老师。。。。。,别的不多说了,下了再看。。。。
hduoj专用解题报告,适合初学者入门,可用!@!!
河南农业大学OJ答案(Java版)
XMU OJ 1230的解题报告和源代码 菜鸟小李是xmu大x的学生了,可英语总数6x。四级考试临近了,临时抱佛脚的他买了本英语词汇,可是小李是个大穷人,随便街摊买了本盗版的新东方。回到宿舍才发现:书里的单词竟然是...
本人搜集的资源,经本人亲测,可用性强!!!适合大家参考...
西北农林科技大学信息学院c++考试题及答案
奥本未来OJ答题系统-答题登录方式.doc 地方干部
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
OJ习题.zip
oj题目源码,你可以轻松AC题目,
这是洛谷OJ题库导出文件,希望大家下载看看
华南农业大学c语言,online judge答案。 如果有需要可以下下载来看看,但只有前十章,剩下两张还没整理,
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助