Dynamic programming solution to the Knapsack problem
Given a list of n integers, A={a1,a2,…,an}, and another integer, k representing the expected sum. Select zero or more numbers from A such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum (k).
Note
- Each element of A can be selected multiple times.
- If no element is selected then the sum is 0.
Source: https://www.hackerrank.com/challenges/unbounded-knapsack