A backpack holds at most W kg. Each of n items has a weight and a value and is either taken or left (no fractions). Maximise the total value.
Write Knapsack. Input: W n, then name weight value lines. Fill the table best[i][w] = best value using the first i items with capacity w (skip vs take), then walk back through the table to list the chosen items in input order. Also compute the greedy answer "best value/weight ratio first" and say whether it is optimal.
For the input
10 4
laptop 6 30
camera 3 14
book 4 16
snack 2 9
the program prints
Best value: 46
Items: [laptop, book] (weight 10 of 10)
Greedy by ratio: 44 (not optimal)
Table cells filled: 44