Greedy Bin Packing
Problem
Finitely many positive integers satisfy condition : each is at most and their total sum is . They are divided into groups, each with sum at most , by the following greedy rule: group picks numbers so that its sum is as large as possible; group then picks from the remaining numbers so that its sum is as large as possible; and so on, with the sum of group for . Over all collections satisfying condition , find the maximum possible value of .
Answer
Solution
| Difficulty | 9/10 |
|---|---|
| Topics | combinatorics, Estimation, Extremal Principle, Casework |
Whiteboard
Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.
Discussion
Ask questions, share alternate solutions, and use LaTeX freely.
Log in to join the discussion.
No comments yet.