Knapsack Problem is classic computer science problem. Each item has different non-negative weights and values. You goal is to take away the most valuable items without exceeding total weight constraint.

Write a method to solve Knapsack Problem with no memorization.
For each item `i`

, it's weight and value are passed in `weight[i]`

and `value[i]`

respectively.
Your method should return an ArrayList of the index of items selected, and the order does not matter.
Note: `i`

starts with `1`

and 0^{th element is zero for simplicity.
}

For example:

[Weight,Value] Item 1 : 50,300 Item 2 : 10,60 Item 3 : 20,90 Item 4 : 40,100 Item 5 : 30,240 Weight Constraint: 60 List of Items Seleted : 2,3,5

Need a **hand?** Try out these hints, one at a time.

public ArrayList<Integer> solve(int[] weights, int[] values, int knapsackWeight, int numberOfElements) { // Values (stored in array values) // Weights (stored in array weights) // Number of distinct items (numberOfElements) // Knapsack capacity (knapsackWeight) }

**C**

**Java**

**Python**