Greedy Bin Packing

Problem

Finitely many positive integers satisfy condition TT: each is at most 77 and their total sum is S=430S = 430. They are divided into MM groups, each with sum at most 2121, by the following greedy rule: group 11 picks numbers so that its sum S1S_1 is as large as possible; group 22 then picks from the remaining numbers so that its sum S2S_2 is as large as possible; and so on, with SiS_i the sum of group ii for i{1,2,,M}i \in \{1, 2, \ldots, M\}. Over all collections satisfying condition TT, find the maximum possible value of MM.

Answer

Solution

Difficulty9/10
Topicscombinatorics, 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.

0 comments
Log in to join the discussion.

No comments yet.