重新排列权重序列的算法

Question

我在一个数组中有许多项目，每个项目都与特定的重量相关联。有一条业务规则规定，任何两个相邻项目的总重量不能超过某个值，为简单起见，假设为 100。

例如，以下是可以的:

[40,60,40,50]

但不是这个(因为 50+60 = 110)

[50,60,40] 

我正在尝试实现一种算法，该算法将重新排列项目(如果可能)以便满足业务规则。例如，第二个可以重新排列为 [60,40,50] 或 [50,40,60]

该算法还应该尽量减少移动项目的数量，即上面的第一个解决方案是最合适的，因为“子排列”[60,40] 得到了维护。

我不是在寻找完整的答案或代码示例，但如果有人可以为此目的指出一些算法或算法类别，我会很高兴。与一些自制的东西相比，依赖现有的和经过验证的算法感觉要好得多。

注意:实际上，项目的数量非常多，因此无法测试所有不同的排列。

Answer 1

不错的贪婪解决方案:首先取最大数。对于每个下一个地方，在满足您的条件之前，从未被占用的数字中取最大值。如果您放置所有数字 - 您已经找到了解决方案。否则解决方案不存在，为什么 - 这对你来说是一个练习。

我的证明:想象存在一个解决方案。显示，我的算法会找到它。让我们 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 也是一个解。它表明算法总能找到解决方案。