The problem
A wagon can carry cap kilograms. Each item (weight, value) can be loaded once or not at all. Return the largest total value that fits. This is the 0/1 knapsack (DYNP-8), but with numbers far too large for a table.
best_value([(1, 2), (10, 15)], 10) # 15
best_value([(6, 30), (5, 24), (5, 24)], 10) # 48
Limits
- Up to 100 items; weights and values up to about 10⁹; cap up to about 5 × 10¹⁰.
- A table by weight or by value is far too big, and trying all 2ⁿ choices is impossible. Branch and bound with a good bound works.
Builds on HARD-3 Branch and bound.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
11 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | No items | Not run | |
| 2 | Nothing fits | Not run | |
| 3 | One item | Not run | |
| 4 | Best value per kilogram goes wrong | Not run | |
| 5 | Two of the second best | Not run | |
| 6 | Items worth nothing | Not run | |
| 7 | Everything fits | Not run | |
| 8 | Thirty items | Not run | |
| 9 | 100 items, values unrelated to weights | Not run | |
| 10 | 100 items, values near the weights | Not run | |
| 11 | 60 items, every value 10⁸ above its weight | Not run |