Best Value Van Load
Problem
A van can carry at most W kilograms. There are several crate types, each with a whole-number weight of at least 1 and a positive value, and the warehouse has as many crates of every type as you want. Return the largest total value you can load without going over W.
Examples
Input: W = 10, crates (weight, value) = [(3, 5), (4, 7), (6, 11)]
Output: 18
Why: one 4 kg crate and one 6 kg crate; three 3 kg crates only reach 15Input: W = 7, crates = [(2, 3), (5, 9)]
Output: 12
Why: 5 kg plus 2 kg beats three 2 kg crates, which are worth 9Input: W = 2, crates = [(3, 5)]
Output: 0
Why: edge case, the only crate is too heavy, so the van leaves emptyHints
0 / 3
Picking crates greedily by value per kilogram can fail: wasting the leftover space can cost more than the best ratio gains.
Think about the best value for every smaller capacity. The best load for capacity c must end with some crate, and what is left is the best load for a smaller capacity.
Fill a table from best[0] up to best[W], starting at zero. For each capacity c and each crate type that fits, best[c] is the larger of its current value and best[c - weight] + value. The answer is best[W].
Solution
Take away any one crate from a best load for capacity c and the rest must be a best load for c minus that crate's weight, so the answers for small capacities build the answers for larger ones. Filling capacities from small to large lets a crate type be used again, because best[c - weight] may already contain crates of the same type. Leaving room unused is covered because the table starts at zero and never goes down. Time is O(W times the number of crate types), and space is O(W).
def best_load(W, crates):
best = [0] * (W + 1) # best[c]: most value within c kg
for c in range(1, W + 1):
for weight, value in crates:
if weight <= c:
best[c] = max(best[c], best[c - weight] + value) # reuse is allowed
return best[W]
print(best_load(10, [(3, 5), (4, 7), (6, 11)])) # -> 18
print(best_load(7, [(2, 3), (5, 9)])) # -> 12
print(best_load(2, [(3, 5)])) # -> 0Stuck on the idea rather than the code? Unbounded Knapsack covers it.