Sunday, September 14, 2014

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