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:
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
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
No comments:
Post a Comment