01 Knapsack Problem : Finding a solution through Dynamic Programming [Java][01Knapsack][Dynamic Programming]

This program finds a solution for a given 01 Knapsack Problem. The solution is based on Dynamic programming. So the time complexity for this program is O(nW). n is the number of items and W is the maximum size of the knapsack. This algorithm is more efficient than the one that uses brute force (checking all the possible combinations). That one has a complexity of O(2^n) [exponential].

Code:

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

public class Knapsack01Dynamic {

    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 printItems() {
        System.out.println("Max benefit: "+table[nItems][capacityKnapsack]);
        System.out.println("Items in the knapsack: ");
        int row = capacityKnapsack;
        for (int i = nItems; i > 0; --i) {

            if (table[i][row] != table[i - 1][row]) {
                System.out.print(i+" ");
                row -= weight[i - 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) {
        Knapsack01Dynamic kd = new Knapsack01Dynamic();
        kd.input();
        kd.B(kd.nItems, kd.capacityKnapsack);
        kd.printTable(); 
        kd.printItems();
    }
}

Sample Output :

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

     0   1   2   3   4   5

0    0   0   0   0   0   0
1    0   0   3  -1  -1   3
2    0   0  -1  -1  -1   7
3    0  -1  -1  -1  -1   7
4    0  -1  -1  -1  -1   7

Max benefit: 7
Items in the knapsack:
2 1