0/1 Knapsack Recursive

Medium

Problem Statement

Maximize total value of items in knapsack with capacity W. Items are either completely included or excluded (0/1 property). Solve using simple recursion.

Examples

1Example 1

Input:

{
  "wt": [
    1,
    2,
    3
  ],
  "val": [
    10,
    15,
    40
  ],
  "W": 6
}

Output:

65

2Example 2

Input:

{
  "wt": [
    1,
    3,
    4,
    5
  ],
  "val": [
    1,
    4,
    5,
    7
  ],
  "W": 7
}

Output:

9

3Example 3

Input:

{
  "wt": [
    4,
    5,
    1
  ],
  "val": [
    1,
    2,
    3
  ],
  "W": 4
}

Output:

3