我有一个问题，要证明以下贪婪算法始终给出正确的解决方案（如果有）。
给定n个盒子，每个盒子都有固定的重量和强度（w，s）。盒子的强度决定了它可以承受的载荷。我们必须形成一堆箱子并将它们一个接一个地排列，以便所有箱子都在堆中。假设有解决该问题的方法，我必须证明我可以始终按照箱子的重量和强度之和从高到低的顺序放到箱子中。这意味着给定n个盒子，我们将始终具有以下内容：w1 + s1> w2 + s2> ...> wn + sn其中box1（w1，s1）位于堆栈的底部，依此类推。
我知道最好的情况是，最重的箱子位于底部，而最大强度的箱子也位于底部。通过运行可以从中始终获得解决方案的多个实例，我看到这种贪婪算法也提供了解决方案。
有什么想法吗？ 预先感谢您的帮助。
我们想证明我们可以按weight + strength升序重新排列任何合法的盒子堆叠。为此，我们需要显示任何连续对，其中
(1) strength(b_i+1) + weight(b_i+1) < strength(b_i) + weight(b_i)
，因为这样我们就可以进行冒泡排序了。换句话说，那
(2) (Sum j=1...i−1 of weight(b_j)) + weight(b_i+1) < strength(b_i)
原始的合法塔楼有
(3) (Sum j=1...i−1 of weight(b_j)) + weight(b_i) ≤ strength(b_i+1)
在两面都添加weight(b_i+1)
(4) (Sum j=1...i−1 of weight(b_j)) + weight(b_i) + weight(b_i+1) ≤ strength(b_i+1) + weight(b_i+1)
用（1）代替右侧
(Sum j=1...i−1 of weight(b_j)) + weight(b_i) + weight(b_i+1) ≤ strength(b_i) + weight(b_i)
取消weight(b_i)：
(Sum j=1...i−1 of weight(b_j)) + weight(b_i+1) ≤ strength(b_i)
“明显”攻击是规范的间接证明：给定存在解决方案，则首先假设贪婪方法不是解决方案。从那里工作到矛盾。
所以...我们给了一系列N的盒子；我们将按照您的问题陈述中的贪婪顺序为它们编号。
合法堆叠是其中所有2 <= i <= n的sum(w(j=i to n)) <= s(i-i)<br>
也就是说，第i-1个盒子可以支撑所有盒子的重量。
鉴于存在合法堆叠，请假设您的贪婪堆叠是不合法的。这告诉您，某些权重条件i不能满足上述权重条件，但对于不同的盒子顺序，可以满足 的要求。从那个工作到关于贪婪盒子排序的矛盾。