You are working for a local supply company. You have shelves of the same width shelf_width and several types of boxes with widths box_widths[]. You’re wondering what’s the maximum utilization of the shelves (the maximum sum of widths of all boxes put on the shelf), assuming there’s an unlimited quantity of each box type.
Now, we need to stock shelves in the warehouse with a limited supply of boxes. For each shelf, we know its width w and the boxes that we want to put on it as the quantity of boxes of each width. For example, 3 boxes of width 3, 2 boxes of width 5, and 1 box of width 7 would be represented as stock = {3: 3, 5: 2, 7: 1}.
Again, your task is to maximize the shelf utilization. It does not matter which boxes will be placed on the shelf, just that they occupy the maximum width.
这道题本质上是一个“尽量装满货架”的背包类问题。给定货架宽度和若干种箱子宽度，需要在不超过货架容量的前提下，让放入的总宽度尽可能大；前半部分是每种箱子数量无限的完全背包思路，后半部分给出每种箱子的库存上限时，则更像有数量限制的背包问题。通常可以用动态规划来求解：状态表示当前能达到的最大占用宽度，转移时尝试加入不同宽度的箱子，最终返回不超过货架宽度的最优值。
