重新排列权重序列的算法
我的数组中有许多项目，每个项目都与特定的权重相关联。有一条业务规则规定，任何两个相邻物品的总重量不能超过某个值，为简单起见，假设为 100。
例如，以下内容是可以的：
[40,60,40,50]
但不是这个（因为 50+60 = 110）
[50,60,40]
我正在尝试实现一种算法，该算法将重新排列项目（如果可能），以便满足业务规则。例如，第二个可以重新排列为 [60,40,50] 或 [50,40,60]
该算法还应该尽量减少移动项目的数量，即上面的第一个解决方案是最合适的，因为“子排列”[60,40] 被维护。
我并不是在寻找完整的答案或代码示例，但如果有人可以为此目的指出一些算法或算法类别，我会很高兴。依赖现有且经过验证的算法比依赖一些自制的算法感觉要好得多。
注意：实际上，项目的数量非常大，因此不能选择测试所有不同的排列。
I have a number of items in an array, each one associated to a certain weight. There is a business rule saying that no two adjacent items cannot have a total weight of more than a certain value, let's say 100 for simplicity.
For example, the following is OK:
[40,60,40,50]
But not this one (since 50+60 = 110)
[50,60,40]
I am trying to implement an algorithm that will rearrange the items (if possible) so that the business rule is fulfilled. For example, the second one could be rearranged to
[60,40,50] or [50,40,60]
The algorithm should also tres to minimize the number of moved items, i.e. the first solution above is most appropriate since the "sub permutation" [60,40] is maintained.
I'm not looking for a complete answer or code examples, but would be happy if someone could point out some algorithms or categories of algorithms for this purpose. It would feel much better to rely on an existing and proved algorithm than some home-made stuff.
Note: In reality, the number of items is very large so testing all different permutations is NOT an option.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
很好的贪心解决方案：对于第一个位置，取最大数量。对于接下来的每个位置，在满足您的条件之前，从未占据的数字中获取最大值。如果您输入了所有数字 - 您就找到了解决方案。否则解决方案不存在，为什么 - 这对你来说是一个练习。
我的证明：想象存在一个解决方案。表明我的算法会找到它。让我们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 也是一个解。它表明算法总能找到解决方案。
Nice greedy solution: for the first place take maximum number. For each next place take maximum from untaken numbers before that satisfy your condition. If you place all numbers - you have found a solution. Otherwise the solution doesn't exist, why - it's an exercise for you.
My proof: imagine a solution exists. Show, that my algorithm will find it. Let's a_1, ..., a_n - any solution. Let a_i - maximum element. Then a_i, a_{i-1}, ..., a_1, a_{i+1}, a_{i+2}, ..., a_n is a solution too, because a_1 <= a_i, a_1 + a_{i+1} <= a_i + a_{i+1}, so (a_i, a_{i+1}) is a good pair. Next, let a_1, ..., a_j is element according to my solution. Show, that a_{j+1} can be element, as my solution suppose to. Let a_i - maximum from a_{j+1}, .., a_n. Then a_1, ..., a_j, a_i, a_{i-1}, ..., a{j+1}, a_{i+1}, ..., a_n is a solution too. It shows that algo always find solution.
大物品只能放在小物品旁边。
示例： [1,3,8,4,2,4,1,7]
我很确定你不能做得比这更好。如果无论如何都违反了业务规则，则没有解决方案。证明/反例留作练习；-)
编辑：首先取最大的项目！
Big items can only be next to small items.
Example: [1,3,8,4,2,4,1,7]
I'm pretty sure you can't do better than this. If the business rule is violated anyway there is no solution. Prove/Counterexample left as an exercise ;-)
Edit: Take biggest item first!
这看起来类似于装箱问题，请看一下（例如）http://en.wikipedia.org /wiki/First_fit_algorithm
我很确定它不一样，但它可能会给你一些线索。
您还需要考虑如果单个项目超出限制会发生什么 - 您将如何处理？
This looks similar to a bin packing problem, take a look at (eg) http://en.wikipedia.org/wiki/First_fit_algorithm
I'm pretty sure it's not the same, but it may give you some clues.
You also need to consider what would happen if a sigle item is over the limit - how would you deal with that?
如果您正在从数据文件中读入并发现异常（大于目标值的值），那么您可以选择终止该程序或排除它。此外，如果先前的解决方案失败，则可以通过切换最后一步来调整 LumpN 提供的解决方案。基本上都是向后推的。
If you're reading in from a data file and find an exception(a value which is larger than the goal value) then you could either choose to kill the program or exclude it. Also, the solution provided by LumpN could be tweaked by switching up the last step if the previous solution failed. Basically shuffling backwards.