public static void maxValue(int maxCapacity, int[] weights, int[] values, int[][] v) {

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

for (int j = 1; j < weights.length + 1; j++) {

if (weights[j - 1] > i) {

v[j][i] = v[j -1][i];

} else {

v[j][i] = Math.max(v[j - 1][i], v[j - 1][i - weights[j - 1]] + values[j - 1]);

}

}

}

}

public static boolean[] includedItems(int[] weights, int[][] v) {

boolean[] items = new boolean[weights.length];

int w = v[0].length - 1;

for (int i = weights.length; i > 0; i--) {

if (v[i][w] == v[i - 1][w]) { items[i - 1] = false; }

else {

items[i - 1] = true;

w -= weights[i - 1];

}

}

return items;

}

public static void main(String[] args) {

final int capacity = 8;

final int[] values = {2, 5, 10, 14, 15};

final int[] weights = {1, 3, 4, 5, 7};

final int[][] v = new int[weights.length + 1][capacity + 1];

System.out.println("Knapsack max weight = " + capacity);

System.out.println("Number of distinct items = " + values.length);

System.out.println("Values = " + Arrays.toString(values));

System.out.println("Weights = " + Arrays.toString(weights));

System.out.println();

maxValue(capacity, weights, values, v);

final int b = v[weights.length][capacity];

System.out.println("v:");

for (int i = 0; i < weights.length + 1; i++) { System.out.println(Arrays.toString(v[i])); }

System.out.println();

System.out.println("Maximum value = " + b);

System.out.println("Items included: " + Arrays.toString(includedItems(weights, v)));

}