创建一堆箱子最优解 [英] Optimal solution for creating a pile of boxes
问题描述
我有一种算法有问题。
有给定的n盒，每一个都有固定的重量和强度（公斤两者给出）。 Box的实力告诉我们，什么是它所能承受的最大重量。我们必须以形成绒头的给定的拖曳（每一个都具有相同的高度）最高。你应该提出一个算法，将永远给一个最优的解决方案，这是k个盒子最长的序列（K＆LT; = N）。
There are given n boxes, each one has fixed weight and strength (both given in kg). Box's strength tells us what is the maximum weight it can bear. We have to form the highest pile of given boxes (each of them has the same height). You should propose an algorithm that will always give an optimal solution, which is the longest sequence of k boxes (k <= n).
嗯，这是一个解决方案，我已经想通了：
Well, that is a solution I have already figured out:
- 首先，排序的所有箱子由他们重量（最重的推移在底部），形成了一堆人。
- 其次，我们认为桩强度（最强的推移在底部）。排序
- 然后，对于每个箱子，从底部开始，我们尝试，只要它的力量能下来把它的底部。
- 在最后，我们必须找出多少盒必须从顶部，这会导致一些箱子下面进行更多的重量比他们的情况被删除。
看来，这个算法工作得很好，但我不知道它是否总是给人最佳的解决方案 - 可能并非如此。我一直想知道的动态解决方案，类似于针对背包问题的解决办法，但我不觉得肯定，如果它可以解决这个样子。有貌似我的问题没有最优子。
It seems that this algorithm works quite well, but I am not sure whether it gives always the optimal solution - probably it doesn't. I have been wondering about the dynamic solution, similar to the solution for knapsack problem, but I don't feel certain if it can be solved this way. There's seemingly no optimal substructure for my problem.
感谢您事先的任何帮助。 ：）
Thank you in advance for any help. :)
推荐答案
在默认情况下，聪明的答案，我会尝试分支定界，从下往上建塔。由于部分建塔，你可以把一个绑定就完成了塔的高度。如果部分造塔能承受X的额外的重量，你可以推断出多少盒，你可以添加之前额外的重量更超过X - 只挑选出其余的框，以增加重量，忽略了自己的实力。如果有零重量箱，把它们放在一边在pre-处理阶段搡他们在上面后。一种不太准确界会为X除以最轻未用盒子的重量。
In default of a cleverer answer, I would try branch and bound, building the tower from the bottom up. Given a partially built tower, you can put a bound on the height of the completed tower. If the partially built tower can sustain an extra weight of X, you can work out how many boxes you could add before the extra weight is more than X - just pick out remaining boxes in order of increasing weight, ignoring their strength. If there are boxes of zero weight, put them aside in a pre-processing stage and shove them on the top later. A less accurate bound would be X divided by the weight of the lightest unused box.
由于这样的束缚，使用回溯搜索来建立你的塔，丢弃所有的部分答案这不可能扩展到产生较高的塔比的最佳答案迄今发现。
Given such a bound, use backtracking search to build your tower, discarding all partial answers which could not possibly be extended to produce a higher tower than the best answer found so far.
这篇关于创建一堆箱子最优解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
