Gifts Knapsack (0/1 Maximize Importance)

Reported in interviews at Jump Trading Meta

Problem statement

You are choosing a subset of gifts to pack. Gift i has weight weights[i] and importance values[i] (both non-negative integers). The bag holds a total weight of at most capacity. Each gift may be taken at most once (0/1). Maximize the total importance of the packed gifts subject to the weight limit, and return that maximum total importance.

Complete:

knapsack(weights: List[int], values: List[int], capacity: int) -> int

Example: weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7 -> take gifts of weight 3 and 4 (importance 4 + 5 = 9) for a total of 9.

Show hint

What quantity could you tabulate for every possible remaining weight so that each gift only needs a take-or-skip decision?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems