Practice: Packing a Carry-On Bag Under a Weight Limit

Five items, a 10 kilo limit, each item packed once: find the best value with one array.

Packing a bag to a weight limit is a 0/1 knapsack, and this exercise asks you to solve one with a single array: choose the loop direction, fill the array item by item, and read off the best value and the items that give it.

A traveller's carry-on allows 10 kilos, and they score how much each item matters to the trip. The book weighs 2 kilos and scores 3, the camera 3 kilos and 7, the laptop 4 kilos and 9, the jacket 5 kilos and 8, and the shoes 3 kilos and 4. Each item is packed whole, at most once.

Keep one array best[c] for capacities 0 to 10, add the items in the order given, and write the array after each one. Decide first which way the inner loop runs. Then give the best score for 10 kilos and say which items make it. Last, check whether packing by score per kilo, highest first, finds the same answer.

Show the arrays, the best score and the items

Each item is packed at most once, so the inner loop runs downwards, from 10 to the item's weight. A run filled the array.

bag_code.pypy

items = [("book", 2, 3), ("camera", 3, 7), ("laptop", 4, 9), ("jacket", 5, 8), ("shoes", 3, 4)]
limit = 10

best = [0] * (limit + 1)
for name, weight, value in items:
    for c in range(limit, weight - 1, -1):
        best[c] = max(best[c], best[c - weight] + value)
    print(f"after {name:<7}{best}")
print(f"best value for {limit} kilos: {best[limit]}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

after book   [0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3]
after camera [0, 0, 3, 7, 7, 10, 10, 10, 10, 10, 10]
after laptop [0, 0, 3, 7, 9, 10, 12, 16, 16, 19, 19]
after jacket [0, 0, 3, 7, 9, 10, 12, 16, 16, 19, 19]
after shoes  [0, 0, 3, 7, 9, 10, 12, 16, 16, 19, 20]
best value for 10 kilos: 20

The best score is 20. The jacket changed nothing, because every capacity already did as well without it. The shoes raised only capacity 10, from 19 to 20, so they are packed, leaving 7 kilos, and the array before them held 16 at capacity 7, the camera and the laptop. A check of all 32 subsets confirmed camera, laptop and shoes, 10 kilos, score 20.

Score per kilo puts the camera first at 2.33, then the laptop at 2.25, the jacket at 1.6, the book at 1.5 and the shoes at 1.33. Packing in that order takes the camera and the laptop, skips the jacket, which no longer fits, and adds the book: 9 kilos and a score of 19, with a kilo of room nobody can use. The run printed both totals.

An upward loop would have let one item be packed more than once. When the question also asks which items, as this one does, keep the arrays or the full table: the last array alone says 20 and nothing more.

← → move through sections and cards