Knapsack (MEDIUM)- Dynamic Programming

Question:

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}.

CODE:

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

    private static int UKS (int value[], int n, int W) {

int arr[] = new int[W + 1], temp = -9999;

arr[0] = 0;

for (int i = 1; i <= W; i++) {

arr[i] = arr[i - 1];

for (int j = 0; j < n; j++) {

if ( value[j]<=i) {

temp = arr[i - value[j]] + value[j];

}

if (temp > arr[i]) {

arr[i] = temp;

}

}

}

return arr[W];

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int m = in.nextInt();

while ((m--) > 0) {

int n = in.nextInt(),/*length*/ W = in.nextInt();//Weight

int [] value = new int[n];

for (int i = 0; i < n; i++) {

value[i] = in.nextInt();

}

System.out.println(UKS(value, n, W));

}

in.close();

}

    

}