KnapSack, repeat selection

This is similar to coin change problem when it allows multiple selections on items.

Given a list of  integers, , and another integer,  representing the expected sum. Select zero or more numbers from  such that the sum of these numbers is as near as possible, but not exceeding, to the expected sum ().

Note

• Each element of  can be selected multiple times.
• If no element is selected then the sum is 0.

Input Format

The first line contains  the number of test cases.
Each test case comprises of two lines. First line contains two integers,  , representing the length of list  and expected sum, respectively. Second line consists of  space separated integers, , representing the elements of list .

Constraints

Output Format

Output  lines, the maximum sum for each test case which is as near as possible, but not exceeding, to the expected sum (k).

Sample Input

2
3 12
1 6 9
5 9
3 4 4 4 8

Sample Output

12
9

Explanation

In the first test case, one can pick {6, 6}. In the second, we can pick {3,3,3}.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

package dp; import java.util.Scanner; public class KanpSack { public static void main(String[] args) { /* * Enter your code here. Read input from STDIN. Print output to STDOUT. * Your class should be named Solution. */ Scanner in = new Scanner(System.in); int t = in.nextInt(); in.nextLine(); for (int i = 0; i < t; i++) { int n = in.nextInt(); int k = in.nextInt(); in.nextLine(); int[] arr = new int[n]; for (int j = 0; j < n; j++) { arr[j] = in.nextInt(); } in.nextLine(); process(arr, k); } in.close(); } private static void process(int[] arr, int k) { int max = maxSum(arr, k); System.out.println(max); } private static int maxSum(int[] arr, int k) { if (arr == null || arr.length == 0) return 0; int[] dpSums = new int[k + 1]; dpSums[0] = 0; // for each sum form small to big for (int i = 1; i <= k; i++) { // for each possible selections, better from small to large for (int j = 0; j < arr.length; j++) { if (arr[j] <= i) {// when available selection is less or equal // than current sum // figure out maximum sum the selections can come up // second part is important, it is previous sum with // possible selection dpSums[i] = Math .max(dpSums[i], arr[j] + dpSums[i - arr[j]]); } } } return dpSums[k]; } }