问题 5478 --天平-【2014暑期训练】T5Day2T1

5478: 天平-【2014暑期训练】T5Day2T1

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

题目描述

天平

【问题描述】

一座天平有n个砝码,每个砝码的重量为Wi(longint以内),按重量从小到大排列,而且从第三个砝码开始,每个砝码重量至少为前两个砝码重量和,即Wi>=Wi-1 + Wi-2

天平的最大承受重量为C(longint以内),称重时选取若干个砝码放到天平上,这些砝码的重量和不能超过这个C。

求最大可以放置的砝码的重量和。

【文件输入】

第一行,两个用空格隔开的整数n,C;

接下来n行,每行有一个整数Wi。

【文件输出】

一个整数,代表最大组合重量

【输入样例】

3 15

1

10

20

【输出样例】

11

【数据规模】

对于20%数据,n<=16;

对于另外的30%数据,C<=100000;

对于100%的数据,n<=1000,C在longint以内

提示

裸的暴力是肯定不能过的,要加剪枝

设当前做到i,组合值为have,

后面所有值的和为sum[i],已得到的最优为ans;



if  have+w[i]>c  then  直接返回

if  have+sum[i]<=ans  then  直接返回



然后,因为越往后砝码重量越大,所以如果从小到大搜索,那么很容易有

Have+sum[i]>ans 第二条剪枝相当于不存在

只要从大到小搜就没有这个问题了。(但第一条剪枝就不能直接返回了)







稳定的2n/2算法

我们发现,对于题目条件的利用还是太少了

Sum[i]表示前缀和

其实有 w[i+2]+w[2]>=sum[i], 即w[i+2]>sum[i]



我们把还能装的容量记为left

则从后往前搜索时有三种情况:

1.  left<w[i],直接不取

2.  left>=w[i]+w[i-1],假设i不取,则w[i]+w[i-1]>w[i-1]+sum[i-2]=sum[i-1],还不如只取i和i-1,换言之,这种情况i砝码必须取。

3.  w[i]<=left<w[i]+w[i-1],i和i+1不能都取,那么假设他们都不取,则w[i]>sum[i-2],还不如只取i,换言之,这种情况必须取i或i-1

第一, 二种情况不浪费复杂度

第三种情况对于两个数有两种选择

则最坏情况下遇到的都是情况三



复杂度为严格的2n/2

来源

 

[提交][状态]