3688: 天平-【2014暑期训练】T5Day2T1
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：1
Description
天平
【问题描述】
一座天平有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以内
HINT
裸的暴力是肯定不能过的，要加剪枝
设当前做到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
设当前做到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