Knapsack with repetitions

DPKnapsack.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

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

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

 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
 */
public class DPKnapsack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        for (int i = 0; i < count; i++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[] array = new int[n];
            for (int j = 0; j < array.length; j++) {
                array[j] = scanner.nextInt();
            }
            List<Integer> result = dpKnapsack(k, array);
            int sum = 0;
            for (Integer integer : result) {
                sum += integer;
            }
            System.out.println(sum);
        }
    }

    private static List<Integer> dpKnapsack(int k, int[] array) {
        //Fill in the array with optimal solution for all numbers from 0 to k
        int[] values = new int[k + 1];
        values[0] = 0;
        for (int i = 1; i < values.length; i++) {
            int pos = -1;
            for (int j = 0; j < array.length; j++) {
                int res = i - array[j];
                if (res >= 0
                        && (values[res] != 0 || res == 0)
                        && (pos == -1 || values[res] < values[pos])) {
                    pos = res;
                }
            }
            values[i] = pos == -1 ? 0 : values[pos] + 1;
        }
        //get nearest possible value that can be created from the input array
        //we can return it as answer but I want to restore all numbers it was created from
        k = 0;
        for (int i = 0; i < values.length; i++) {
           if (values[i] > 0){
               k = i;
           }
        }

        //restore all numbers that creates our answer
        List<Integer> result = new ArrayList<>();
        while (k > 0) {
            int pos = -1;
            int v = -1;
            for (int i = 0; i < array.length; i++) {
                int res = k - array[i];
                if (res >= 0
                        && (values[res] != 0 || res == 0)
                        && (pos == -1 || values[res] < values[pos])) {
                    pos = res;
                    v = array[i];
                }
            }
            if (v > 0) {
                result.add(v);
                k -= v;
            }
        }

        return result;
    }
}