0/1 Knapsack Memoization

Medium

Use recursion with memoization (top-down DP) to solve 0/1 Knapsack efficiently by avoiding repeated work of overlapping subproblems.

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