SDUT 2408 Pick apples

一开始以为是完全背包问题,但是背包的体积V太大,直接背包果断不过。 

  正解应该是 大范围贪心,小范围背包。

  直接谈心不能保证充分利用背包的体积,从而不能保证找到最优解。

  但是背包找到的最优解也肯定是尽可能将性价比高的物品放进去。

  这样答题思路就出来了,先分出一部分空间 V1 来用来贪心,剩余部分 V2 = V - V1用来背包,贪心即选择性价比最高的物品放进去。

  如果贪心后 V1 有剩余的空间 , 设剩余空间为V3,则应将V3回收用来背包,即 V2 += V3。

  这样得出的结构就是正确答案了。

  但是这里还牵扯到一个问题,那就是V1和V2的划分问题。

  这里有两种方法,一种就是直接分出较大的一部分空间来用来背包,显然此部分要在时间和空间上都能承受。

  还有一种就是找给出的这三个体积的最小公倍数,至于为什么这样能行,我也不知道了,坐等大神来证明 o(∩_∩)o 

原文地址:https://www.cnblogs.com/tsw123/p/4420384.html