Skip to main content

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();
}
    
}

Comments