comments (1)
Neon Coder2026-10-12
Oooh this is fun
Output will appear here...
A thief has a bag that can carry at most capacity kilograms. There are several items, each with a weight and a value, and each item can be taken at most once.
Write a function knapsack(capacity, weights, values) that returns the largest total value the thief can carry. For example, with capacity 50, weights [10, 20, 30] and values [60, 100, 120], the best choice is the second and third items for a value of 220.
Tip
Let best[w] be the best value achievable with weight limit w. For each item, update best from the highest weight down to the item's weight. Going downwards makes sure the same item isn't used twice.
The starter code reads the capacity, then the weights, then the values (one line each).
Neon Coder2026-10-12Oooh this is fun