Unbounded Knapsack

Medium

Problem Statement

Given weights and values of n items, and a knapsack capacity W, find the maximum value of items that can be put in the knapsack if an unlimited number of instances of each item can be used.

Examples

1Example 1

Input:

{
  "wt": [
    1,
    3,
    4,
    5
  ],
  "val": [
    10,
    40,
    50,
    70
  ],
  "W": 8
}

Output:

110

2Example 2

Input:

{
  "wt": [
    2,
    3,
    7
  ],
  "val": [
    5,
    8,
    10
  ],
  "W": 10
}

Output:

26

3Example 3

Input:

{
  "wt": [
    1
  ],
  "val": [
    10
  ],
  "W": 5
}

Output:

50