0-1 Knapsack in Java

Question

I'm looking for advice on coding practices in general.

 public class Knapsack {
 public static int getMaxBenefit(int[] weights, int[] benefits, int capacity) {
 int[][] maxbenefit = new int[weights.length + 1][capacity + 1];
 for (int i = 0; i <= weights.length; i++)
 maxbenefit[i][0] = 0;
 for (int i = 0; i <= capacity; i++)
 maxbenefit[0][i] = 0;
 for (int item = 1; item <= weights.length; item++) {
 for (int weight = 1; weight <= capacity; weight++) {
 if (weights[item - 1] <= weight) {
 int option1 = benefits[item - 1] + maxbenefit[item - 1][weight - weights[item - 1]];
 int option2 = maxbenefit[item - 1][weight];
 maxbenefit[item][weight] = Math.max(option1, option2);
 } else {
 maxbenefit[item][weight] = maxbenefit[item - 1][weight];
 }
 }
 // printMatrix(maxbenefit, weights.length, capacity);
 }
 printMatrix(maxbenefit, weights.length, capacity);
 return maxbenefit[weights.length][capacity];
 }
 public static void printMatrix(int[][] matrix, int R, int C) {
 for (int i = 0; i <= R; i++) {
 for (int j = 0; j <= C; j++) {
 System.out.print(matrix[i][j] + " | ");
 }
 System.out.println();
 }
 }
 public static void main(String[] args) {
 int[] weights = new int[] { 2, 3, 4, 5, 6 };
 int[] benefit = new int[] { 3, 4, 8, 9, 9 };
 getMaxBenefit(weights, benefit, 5);
 }
}

Answer 1

 int[][] maxbenefit = new int[weights.length + 1][capacity + 1];
 for (int i = 0; i <= weights.length; i++)
 maxbenefit[i][0] = 0;
 for (int i = 0; i <= capacity; i++)
 maxbenefit[0][i] = 0;

There is no need to initialize part of the array as 0, because the entire array starts off as 0.

public static void printMatrix(int[][] matrix, int R, int C) {
 for (int i = 0; i <= R; i++) {
 for (int j = 0; j <= C; j++) {
 System.out.print(matrix[i][j] + " | ");
 }
 System.out.println();
 }
}

In here, you should check if R and C don't exceed matrix.length and matrix[i].length respectively. That way you can either limit the printing, or you could throw an error with explanation, rather than running into ArrayIndexOutOfBoundsException.

In the same way, you should check the size of int[] benefits in getMaxBenefit, because if the weights and the benefits are not the same size then you'll throw an error at some point, and failing fast is better.