Deviopath › TypeScript

Pack the Backpack (0/1 Knapsack)

Hard · Algorithms

Write pack(items, capacity) that chooses items (each at most once) with a total weight of at most capacity and the largest possible total value.

Return { value, items } where items are the names of the chosen items in their ORIGINAL order. Weights are positive integers. The tests are built so that the best selection is unique.

Hint: build a dynamic-programming table best[i][c] = best value using the first i items with capacity c, then walk back through it to find which items were taken.

Next: Weighted Job Scheduling