解决此问题的最佳算法是什么？我在这个问题上花了几个小时。但无法解决。对数值进行分类的算法
一个男人购买了一条项链，并计划将它分成两部分，每部分的平均亮度应该大于或等于原始部分。
用于将项链的标准是在珍珠的数目
1.差两个珍珠之间套不应珍珠在原项链的数量或3取高者的大于10％。
2.两个项链中珍珠数量的差异应该是最小的。
3.如果任何一条项链的平均亮度小于原始设置的平均亮度，则返回0作为输出。
4.两个项链的平均亮度应该大于原来的两个，两块的平均亮度之差最小。
5.每件的平均亮度应大于或等于原件。
这个问题很难有效地做到（在NP某处）。
假设你有一组平均值为X。那就是，X = (x1 + x2 + ... + xn)/n。
假设您将它分成平均分别为S和T的集合，其中s和t项目分别在每个集合中。
您可以用数学证明，如果平均的一个，S或T，比X越大，其他两个必须小于X。
因此，两组必须具有完全相同的亮度，因为这是您的条件可满足的唯一方法。
知道了这一点，你最后的sumset sum问题 - 你想找到一个子集，其总和恰好是整个集合的一半。这是一个众所周知的难题。 （它已被归类为NP，好吧，它与子集和问题并不完全相同，但是如果从每个亮度值中减去全集的平均值，则解决子集和问题会给出答案。相反，看你如何解决你的问题的子集总和问题。）
因此，没有快速的方法做到这一点 - 只有近似值或指数运行时间...但是，也许this将帮助。它提到更好运行时间如果你的权重（在你的情况下，亮度水平）是有界的
告诉我们你是如何测量“亮度”，因为规范的计算平均值的方式将使分区的平均值的平均值无法大于平均值本身艺术比原来的平均水平高，另一部分必须低一些 - 也就是说，你必须把项链分成两半，以达到你想要的结果。 – Kaganar 2012-03-30 20:15:44
@Kaganar - 输入值将是一组数字，例如 - {10,6,3,9,7,2,5,8,4,1}，其中0≤亮度≤10。 – eler 2012-03-30 20:19:09
你打算把这个分成两部分，每部分的平均值等于或大于原始平均值？ – Kaganar 2012-03-30 20:20:06