算法面试题：百分比分配.

tarside

有一1000个重量不一样的草果，按重量的百分比分给7个人，
例如：
用户A占总重量的10%,
用户B占总重量的05%,
用户C占总重量的25%,
用户D占总重量的20%,
用户E占总重量的15%,
用户F占总重量的10%,
用户G占总重量的15%,
共 100% 刚好分完。
求最佳的分配，上下浮动最小。

塑料袋

我想知道

要是999个草果加在一起重1克，另一个草果重999克，这种情况下，怎么分才叫做最佳？？？

tarside

呵呵。 塑料袋说得好，算法的最坏情况时问题。

只是想虚心求教下正常情况下的算法。 正常情况下的水果重量应该不会相差这么大。

_Rayx

回复 1# tarside


    所谓的最佳分配方案又是什么呢？是各个人与分配比之差和最小还是方差最小呢？

cdtits

题目比较有歧义

hbmhalley

有1000个重量不一的草果，按重量的百分比分配给 2 个人，怎样分配浮动最小？


要是没记错，这个问题似乎np?

7个人??

shang2010

dp代码看起来都挺恶心的，而且思维很抽象


难以理解，就是 DP

tarside

回复 4# _Rayx


如：分配给用户A占总重量的10%,  可能分配的草果重量不会绝对等于10%， 大多数是约等于 10%, 如： 9.9134% ;

tarside

难道高手都没空? 背包问题

sb_oy

个人这么理解，全部糖果质量求平均值，对糖果质量排序，两头求和，根据质量取舍大的部分或小的部分