Deadline-Aware Bin Packing

Background. Pack sized, valued items into a fixed sequence of bins. Each bin has a finite integer capacity and a fixed index (0..B-1). Each item has a size, a value and a soft deadline expressed as a bin-index threshold: assigning an item to a bin with index greater than its deadline is allowed but incurs a lateness penalty. Dropping an item (assigning None) is also allowed but incurs a drop penalty. The objective trades keeping items on-time, tolerating late placements, and possibly dropping items to maximize a linear score.

Implement the solve(instance) function in solution.py.

INPUT FORMAT

• instance: lib.Instance with fields:
  • bins: List[int] — capacities for bins indexed 0..B-1 (each a positive int).
  • items: List[lib.Item] — each item is an object with attributes (item.size, item.value, item.deadline):
    • size: int (>0) — space required in a single bin.
    • value: int (>0) — contribution to the objective when kept (subject to penalties).
    • deadline: int (>=0) — latest bin index for on-time placement; bins with index > deadline cause the item to be considered LATE.
  • late_penalty_factor: float (>=0) — multiplier applied to the total value of LATE items.
  • drop_penalty_factor: float (>=0) — multiplier applied to the total value of DROPPED items.
  • name: optional string (ignored by scoring).

OUTPUT FORMAT

• Return a list of length len(items). For each item index i the entry must be either:
  • an integer j with 0 <= j < len(bins) indicating the bin index item i is assigned to, or
  • None to indicate the item is dropped.
• Validity rules:
  • Each item must be assigned exactly one of (int bin index) or None.
  • For every bin, the sum of sizes of items assigned to that bin must not exceed that bin's capacity.

SCORING (higher is better)

• Let S_on be the sum of values for items assigned to bins with index <= item.deadline (on-time).
• Let S_late be the sum of values for items assigned to bins with index > item.deadline (late).
• Let S_drop be the sum of values for items assigned None (dropped).
• Score = S_on - late_penalty_factor * S_late - drop_penalty_factor * S_drop.
• Maximize this score. Late placements and drops reduce the objective by their respective penalty factors multiplied by the items' values.

WORKED EXAMPLE

Input (JSON): { "bins": [5, 5, 5], "items": [ {"size": 2, "value": 10, "deadline": 0}, {"size": 3, "value": 8, "deadline": 1}, {"size": 4, "value": 6, "deadline": 0}, {"size": 2, "value": 5, "deadline": 2} ], "late_penalty_factor": 1.0, "drop_penalty_factor": 2.0, "name": "example-1" }

A valid return value (Python list): [0, 1, 2, 0]

This assignment respects bin capacities (bin loads: bin0=2+2=4, bin1=3, bin2=4) and places item 2 late (bin 2 > deadline 0). No items are dropped.

Submit runs solve() on several generated instance sets (their sizes are in the constraints). For each set, the average score must reach a fixed threshold; the exact optimum is not required.

Done when Submit goes green.

Input: {"bins": [5, 5, 5], "items": [{"size": 2, "value": 10, "deadline": 0}, {"size": 3, "value": 8, "deadline": 1}, {"size": 4, "value": 6, "deadline": 0}, {"size": 2, "value": 5, "deadline": 2}], "late_penalty_factor": 1.0, "drop_penalty_factor": 2.0, "name": "ex1"}

Output: [0, 1, 2, 0]

Input: {"bins": [3, 3], "items": [{"size": 2, "value": 5, "deadline": 0}, {"size": 2, "value": 4, "deadline": 0}, {"size": 2, "value": 7, "deadline": 1}], "late_penalty_factor": 0.5, "drop_penalty_factor": 1.5}

Output: [0, null, 1]