public class KnapSackMaxValueUnbound {
    public static void main(String[] args) {
        KnapSackMaxValueUnbound ku = new KnapSackMaxValueUnbound();
        int[] w = { 6, 3, 4, 2 };
        int[] v = { 30, 14, 16, 9 };
        int capacity = 10;
        ku.unboundKnapsack(w, v, capacity);
    }

    public List<Integer> unboundKnapsack(int[] w, int[] v, int capacity) {
        List<Integer> result = new ArrayList<>();
        if (capacity < 0 || w == null || v == null || w.length != v.length) {
            return result;
        }
        int[] k = new int[capacity + 1];
        int[] s = new int[capacity + 1];
        int[] prev = new int[capacity + 1];
        k[0] = 0;
        for (int i = 0; i < w.length; i++) {
            s[i] = -1;
            prev[i] = -1;
        }

        for (int b = 1; b < k.length; b++) {
            for (int i = 0; i < w.length; i++) {
                if (w[i] <= b && k[b] < v[i] + k[b - w[i]]) {
                    k[b] = v[i] + k[b - w[i]];
                    s[b] = i;
                    prev[b] = b - w[i];
                }
            }
        }
        System.out.println(Arrays.toString(k));
        System.out.println(Arrays.toString(s));
        System.out.println(Arrays.toString(prev));
        // s[b] + 1
        int n = k.length - 1;
        while (s[n] != -1) {
            result.add(s[n] + 1);
            n = prev[n];
        }
        Collections.reverse(result);
        System.out.println(result);
        return result;

    }
}