Ozz*_*zzy 8 algorithm sequence
我有一些数组中的项目,每个项目都与一定的权重相关联.有一条商业规则说没有两个相邻的商品的总重量不能超过某个值,简单来说就是100.
例如,以下是可以的:
[40,60,40,50]
但不是这个(因为50 + 60 = 110)
[50,60,40]
我正在尝试实现一种算法,该算法将重新排列项目(如果可能),以便实现业务规则.例如,第二个可以重新排列为[60,40,50]或[50,40,60]
该算法还应该尽量减少移动项目的数量,即上面的第一个解决方案是最合适的,因为维持了"子置换"[60,40].
我不是在寻找完整的答案或代码示例,但如果有人可以为此目的指出一些算法或算法类别,我会很高兴.依靠现有的和经证实的算法比一些自制的东西要好得多;)
注意:实际上,项目数量非常大,因此测试所有不同的排列不是一种选择.
好贪心的解决方案:首先取最大数量.对于每个下一个地方,在满足您的条件之前从最大数字中取出最大值.如果您放置所有数字 - 您已找到解决方案.否则解决方案不存在,为什么 - 这对你来说是一个练习.
我的证明:想象一个解决方案存在.显示,我的算法会找到它.让我们a_1,...,a_n - 任何解决方案.设a_i - 最大元素.那么a_i,a_ {i-1},...,a_1,a_ {i + 1},a_ {i + 2},...,a_n也是一个解决方案,因为a_1 <= a_i,a_1 + a_ { i + 1} <= a_i + a_ {i + 1},所以(a_i,a_ {i + 1})是一对好的.接下来,根据我的解决方案,让a_1,...,a_j是元素.显示,a_ {j + 1}可以是元素,正如我的解决方案所假设的那样.设a_i - 来自a_ {j + 1},..,a_n的最大值.然后a_1,...,a_j,a_i,a_ {i-1},...,a {j + 1},a_ {i + 1},...,a_n也是一个解决方案.它表明算法总能找到解决方案.