Maximum Apples That Fit in a Box
There is a box with a capacity of 5000 grams. The box may already hold some items, which reduces the room left. You will add apples until the box is full.
You are given a zero-indexed array $A$ of $N$ integers. The first element $A[0] = K$ is the total weight already in the box; the remaining elements are individual apple weights. Implement the function max_apples(A) that returns the maximum number of apples that can be added without exceeding the 5000 gram capacity.
Constraints
- $1 \le N \le 100$
- Every value is between 0 and 5000
- Maximize the COUNT of apples, not the total weight
Examples
- $A = [4650, 150, 150, 150] \to 2$ (room left is 350g, so two 150g apples fit, total 4950)
- $A = [4850, 100, 30, 30, 100, 50, 100] \to 3$ (pick 30, 30, 50)
Example
max_apples([4850, 100, 30, 30, 100, 50, 100]) -> 3
The box already holds 4850g, leaving 150g of room. Sorting the apples ascending (30, 30, 50, 100, 100, 100) and greedily taking the lightest fits 30 + 30 + 50 = 110g, for 3 apples; a fourth (100g) would exceed the 150g of room.
Hints
- The objective is number of apples, not weight. Which apples should you prefer?
- Sort the apples by weight ascending; a greedy exchange argument proves taking the lightest first is optimal.
- Remember the first array element is the existing load, so the room available is $5000 - A[0]$, not 5000.
Worked Solution
How to Think About It: You want the most apples, not the heaviest load, so you should always prefer light apples. This is the classic greedy exchange argument: if an optimal solution skipped a light apple in favor of a heavier one, swapping in the lighter apple never increases total weight and keeps the count the same, so sorting ascending and taking apples until you run out of room is optimal.
Algorithm: Compute remaining capacity $5000 - K$ where $K = A[0]$. Sort the apple weights ($A[1:]$) ascending. Walk through them, subtracting each weight from the remaining capacity while it still fits, counting apples.
Code: ```python def max_apples(A): # A[0] = weight already in the box; A[1:] = individual apple weights. # Box capacity is 5000 grams. Greedily take the lightest apples. remaining = 5000 - A[0] count = 0 for w in sorted(A[1:]): if w <= remaining: remaining -= w count += 1 else: break return count ```
Complexity: $O(N \log N)$ for the sort, $O(N)$ scan.
Answer: Sort apples ascending and greedily take the lightest ones until the box is full -- the maximum count.
Intuition
This is a fractional-feeling problem that is actually pure greedy because all you maximize is count. The subtle bug that trips candidates is the input format: the first element is pre-existing weight that must be subtracted, and a naive solution that treats every element as an apple gets the wrong answer. Whenever you maximize a count under a single linear budget, sort by cost and take cheapest-first -- the same logic powers activity-selection and many resource-packing heuristics in real systems.