Responsive image

问题 1131 --载重问题

1131: 载重问题

时间限制: 3 Sec  内存限制: 128 MB
提交: 2  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

有一批概共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,第一只船尽可能装满


来源

[提交][状态]
ACM算法攻关部