01 Knapsack Problem Print All Solutions using Dynamic Programming [01 Knapsack][Dynamic Programming][All Solutions][Java]

This program uses Dynamic Programming to solve the 01 Knapsack problem and prints all the possible solutions to a given problem. All solution printer is a separate recursive function. Also displays a nicely formatted table constructed during evaluation of the problem.

Code:

import java.util.Arrays;
import java.util.Scanner;

public class Knapsack01DynamicAllSolutions {

    int[][] table;
    int[] weight;
    int[] benefit;
    int capacityKnapsack;
    int nItems;

    Scanner scan = new Scanner(System.in);

    int B(int items, int maxCapacity) {

        if (maxCapacity < 0 || items < 0) {
            return -2;
        }

        if (table[items][maxCapacity] != -1) {
            return table[items][maxCapacity];
        }

        int arg1 = B(items - 1, maxCapacity);
        int arg2 = B(items - 1, (maxCapacity - weight[items - 1]));
        if (arg2 == -2) {
            arg2 = 0;
        } else {
            arg2 += benefit[items - 1];
        }
        table[items][maxCapacity] = Math.max(arg1, arg2);
        return table[items][maxCapacity];
    }

    void printAllItems(int row, int col) {
        if (row == 0) { return; }
        
        while (table[row][col] == table[row - 1][col]) {
            int number = col - weight[row - 1];
            int ben = benefit[row - 1];

            if(number==0 && benefit[row-1] == table[row-1][col]){System.out.print("[ "+row+" ] ");}
            if (number <= 0) {
                ben = 0;
                number = 0;
            }
            if (table[row][col] == table[row - 1][number] + ben) {
                //include this item  
                System.out.print("[ ");
                System.out.print(row + " ");
                printAllItems(row - 1, col - weight[row - 1]);
                System.out.print("] ");
            } 
            row--;
            if (row == 1) {
                break;
            }
        }

        if (table[row][col] != table[row - 1][col]) {
            System.out.print(row + " "); 

            if (col - weight[row - 1] > 0) {
                printAllItems(row - 1, col - weight[row - 1]); 
                
            }
        }
    }  

    void input() {
        System.out.println("Enter the number of items: ");
        nItems = scan.nextInt();

        System.out.println("Enter the (weight and benefit)s of the n items: ");

        weight = new int[nItems];
        benefit = new int[nItems];

        for (int i = 0; i < nItems; ++i) {
            weight[i] = scan.nextInt();
            benefit[i] = scan.nextInt();
        }

        System.out.println("Max capacity of the knapsack: ");
        capacityKnapsack = scan.nextInt();
        table = new int[nItems + 1][capacityKnapsack + 1];

        for (int i = 1; i < nItems + 1; ++i) {
            Arrays.fill(table[i], -1);
        }
        for (int i = 0; i < nItems + 1; ++i) {
            table[i][0] = 0;
        }
    }

    void printTable() {
        System.out.println();
        System.out.print("   ");
        int count = 0;
        for (int i = 0; i < capacityKnapsack + 1; ++i) {
            System.out.printf("%3d ", i);
        }
        System.out.println("\n");
        for (int i = 0; i < nItems + 1; ++i) {
            System.out.printf("%-3d", count);
            for (int j = 0; j < capacityKnapsack + 1; ++j) {
                System.out.printf("%1$3d ", table[i][j]);
            }
            count++;
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Knapsack01DynamicAllSolutions kd = new Knapsack01DynamicAllSolutions();
        kd.input();
        kd.B(kd.nItems, kd.capacityKnapsack);
        kd.printTable(); 
        kd.printAllItems(kd.nItems, kd.capacityKnapsack);
    }
}

Output:

Enter the number of items:
6
Enter the (weight and benefit)s of the n items:
2 3
2 1
1 3
3 4
5 3
2 1
Max capacity of the knapsack:
8

     0   1   2   3   4   5   6   7   8

0    0   0   0   0   0   0   0   0   0
1    0   0   3   3   3   3   3   3   3
2    0   0   3   3   4   4   4   4   4
3    0   3  -1   6  -1   7   7  -1   7
4    0   3  -1   6  -1  -1  10  -1  11
5    0  -1  -1  -1  -1  -1  10  -1  11
6    0  -1  -1  -1  -1  -1  -1  -1  11 

[ 6 4 3 1 ] 4 3 2 1

The max size is therefore 11 and possible item combinations are:

6 4 3 1 and
4 3 2 1