algorithm - 贪心在线装箱算法

Question

我正在尝试为在线垃圾箱打包问题找到一个贪婪的解决方案。与原来的装箱问题相比，这个问题有一些变化。首先，每个箱子的容量 C > 0。此外，每个物品 i 的重量 w_i <= C。由于这是一个在线箱子包装问题，因此在下一个物品可以之前，每个物品都必须放在一个箱子中（并且永远不会再次移动）被处理。此外，如果我们创建了一个新的 bin，那么以后我们就不能返回旧的 bin 并在其中放置更多的项目。

我的贪心算法是下一个拟合解决方案（在总重量小于 C 的情况下将尽可能多的项目放入一个箱中）。当我们无法容纳下一个项目时，我们创建一个新的 bin。

但是我很难证明这个解决方案的最优性。我尝试使用贪婪的提前论点，但被卡住了。

任何提示或指南都会很棒！

标签： algorithmoptimizationgreedybin