有一批概共N个集装箱要装上两只载重量分别为W1和W2的轮船,其中,集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这N个集装箱装上这两艘轮船。如果有,找出一种方案;
例如,当N=3,W1=W2=50,且w=[10,40,40]时,可将集装箱1和集装箱2装上一艘轮船,而将集装箱3装在第二艘轮船;如果w=[20,40,40],则无法将这3个集装箱都装上轮船。
有一批概共N个集装箱要装上两只载重量分别为W1和W2的轮船,其中,集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这N个集装箱装上这两艘轮船。如果有,找出一种方案;
例如,当N=3,W1=W2=50,且w=[10,40,40]时,可将集装箱1和集装箱2装上一艘轮船,而将集装箱3装在第二艘轮船;如果w=[20,40,40],则无法将这3个集装箱都装上轮船。
输入的第一行是三个整形变量W1,W2,N。分别代表船1,船2的载重和集装箱的数量。( 载重<= 300000,N<=30)
第二行是是N个整形变量w[i],分别代表集装箱的重量;(w[i]<=300000)
对于每个结果输出,
1,如果存在使集装箱全部装完的方法,则输出两行:
第一行输出:Yes
第二行输出:第一只船的实际载重 第二只船的实际载重
2,如果不能将全部集装箱装上两只船,则输出一行:
第一行输出:No
50 50 3
10 40 40
Yes
50 40
1,回溯法
2,第一只船尽可能装满
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部cnt: 3089
关于网站改版