dsa · medium

0/1 Knapsack

GreyOrangeDynamic Programming

weights[i] and values[i] for n items; capacity W. Each item at most once. Return max value.

Arguments

• weights — item weights; weights[i] is item i
• values — item values; values[i] is item i
• W — knapsack capacity

**Example**

`` Input: [1,3,4] [15,20,30] 4 Output: 35 ``

Constraints

1 <= n <= 100, 0 <= W <= 1000 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.

Examples

Example 1

Input:
[1,3,4]
[15,20,30]
4

Expected:
35

Open in the Dojo editor