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.
This problem is about maximizing shelf utilization without exceeding the shelf width, which is a classic knapsack-style optimization. In the unlimited case, it maps to complete knapsack; with limited stock per box width, it becomes a bounded knapsack variant. The key is to use dynamic programming to track the best achievable filled width for each capacity and update it with each box type, then return the maximum width that fits.
