## Saturday, September 13, 2014

### 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