Best sum without going over
Track every reachable sum as before, then read off the largest one that doesn't exceed the limit. About 11 minutes.
Fill the suitcase as close to the limit as you can
Your suitcase takes at most 15 kg, and your bags weigh 4, 6 and 8 kg. You can't split a bag. What's the heaviest load you can pack without going over?
Build the same checklist of possible totals, up to the limit. It tells you every load you could pack. Totals over the limit are simply never written down.
Same table as before, with the limit as the last column. Only 0 to start.
Read it from the top
Once every bag has been considered, look at the checklist from the limit downward. The first ticked total you meet is the answer: the heaviest load that still fits.
For 4, 6 and 8 with a 15 kg limit, 15 isn't possible but 14 is (6 + 8). All three bags would be 18, too heavy.
can = [True] + [False] * limit
for x in nums:
for s in range(limit, x - 1, -1):
if can[s - x]:
can[s] = True
for s in range(limit, -1, -1):
if can[s]:
return sBags weigh 4, 6 and 8 kg and the suitcase holds 15 kg. What's the heaviest load that fits?
- A14 kg
- B15 kg
Show the answer
14 kg. 6 + 8 = 14 fits. All three is 18, too much, and no combination makes exactly 15.
Best sum without going over
Given an array nums of non-negative integers and a limit, return the largest possible sum of some subset of nums that does not exceed limit.
nums = [4, 6, 8], limit = 15 → 14
0 ≤ nums.length ≤ 200 · 0 ≤ nums[i] ≤ 1,000 · 0 ≤ limit ≤ 10,000