c - 在包装n个最大容量为W的箱子时，要最小化箱子的数量，同时还要将浪费的箱子空间最小化？

Closed. This question is off-topic。它当前不接受答案。
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。
                        
                        2年前关闭。
                                                                                            
                
        
因此，您想将重量为w_i的n个物品包装到最大重量为W的箱中。

就像您的一般装箱问题一样，但以下约束使其变得不同（可能更容易）：


这些项目以w_1，...，w_i，...，w_n的顺序给出，在考虑下一个项目之前，必须先放置第一个项目。


最后，您还希望最小化每个存储箱中浪费的空间。这是由目标函数定义的-用外行人的话来说，通常的行为是这样的：如果仅浪费少于或等于5％的垃圾箱，您可以罚款，并且不会被记录下来。否则，如果浪费了5％以上，则会记录下来，而您不希望这样做。

目标：减少使用的垃圾箱数量，同时将浪费的空间降至最低。优先考虑的是首先减少垃圾箱的数量。

最好的算法/方法是什么？



我不太确定这是否是装箱问题的变体，但我问它是否仍然存在。如果你们知道哪个问题更合适，请告诉我。

另外，我想知道我可以用来解决此类问题的所有可能方法（动态编程或贪婪方法）。

一些未实现的尝试解决方案：


我尝试了类似于First Fit算法的贪婪方法，但它并不总是能获得最佳解决方案。有时，浪费的空间不会总是最小化的，因为没有考虑其他组合。 （这些其他组合浪费的空间更少）
我还考虑了Dijkstra算法的某些变体，只专注于最小化空间浪费。但是，这次，我发现它并不总是产生最小数量的垃圾箱。


就是这样到目前为止，我只尝试过贪婪的方法，因为我希望有一种简单的方法来解决它。如果没有，请赐教。即使事实真相令人痛心，我也会接受。谢谢！

编辑：
我只想知道使用其他贪婪方法是否可以解决。另外，我想知道我可以搜索和学习哪些常规问题，以便可以帮助我解决该问题。

最佳答案

“首先放置的物品必须在考虑下一个物品之前放置” –这意味着您已被塞满。您所能做的就是猜测。

我想说的是，每件物品到达时，您首先要检查是否有一个垃圾箱，将垃圾从> 5％浪费到≤5％，然后将其放在那儿，然后再检查是否有一个垃圾箱适合该物品并将其放入在那里，如果它不适合任何地方，则将其放入新的垃圾箱中。

整个标准似乎有点可笑。为什么三个装满96％，94.5％，94.5％的垃圾箱要比三个装满95％，95％和95％的垃圾箱差？基本上，这意味着您要填充刚好高于95％的垃圾箱，因为如果填充1到100％，则可能意味着另一个垃圾箱低于95％。直到您需要一个新的料槽为止，因为所有这些缺口都接近5％。

关于c - 在包装n个最大容量为W的箱子时，要最小化箱子的数量，同时还要将浪费的箱子空间最小化？ ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43434797/