SDUT 2408 Pick apples
浏览数：32 /
时间：2015年06月11日
一开始以为是完全背包问题，但是背包的体积V太大，直接背包果断不过。
正解应该是 大范围贪心，小范围背包。
直接谈心不能保证充分利用背包的体积，从而不能保证找到最优解。
但是背包找到的最优解也肯定是尽可能将性价比高的物品放进去。
这样答题思路就出来了，先分出一部分空间 V1 来用来贪心，剩余部分 V2 = V - V1用来背包，贪心即选择性价比最高的物品放进去。
如果贪心后 V1 有剩余的空间 ， 设剩余空间为V3，则应将V3回收用来背包，即 V2 += V3。
这样得出的结构就是正确答案了。
但是这里还牵扯到一个问题，那就是V1和V2的划分问题。
这里有两种方法，一种就是直接分出较大的一部分空间来用来背包，显然此部分要在时间和空间上都能承受。
还有一种就是找给出的这三个体积的最小公倍数，至于为什么这样能行，我也不知道了，坐等大神来证明 o(∩_∩)o
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
