-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKnapsackProblem.java
More file actions
109 lines (95 loc) · 4.24 KB
/
KnapsackProblem.java
File metadata and controls
109 lines (95 loc) · 4.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package algorithm.DynamicProgramming;
/**
* The Knapsack problem.
*/
public class KnapsackProblem
{
/**
* Knap sack int.
*
* @param profits the profits
* @param profitsLength the profits length
* @param weights the weights
* @param weightsLength the weights length
* @param capacity the capacity
* @param currentIndex the current index
* @return the int
*/
public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity ,int currentIndex)
{
// Base Case
if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
return 0;
// If weight of the nth item is more than Knapsack capacity W, then
// this item cannot be included in the optimal solution
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapSack(profits, profitsLength, weights, weightsLength, capacity - weights[currentIndex], currentIndex + 1);
int profit2 = knapSack(profits, profitsLength, weights, weightsLength, capacity, currentIndex + 1);
// Return the maximum of two cases:
return Math.max(profit1, profit2);
}
/**
* Knapsack recursive int.
*
* @param lookupTable the lookup table
* @param profits the profits
* @param profitsLength the profits length
* @param weights the weights
* @param weightsLength the weights length
* @param capacity the capacity
* @param currentIndex the current index
* @return the int
*/
public static int knapsackRecursive(int [][] lookupTable, int profits[], int profitsLength, int weights[], int weightsLength, int capacity, int currentIndex) {
// base checks
if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
return 0;
// if we have already solved the problem, return the result from the table
if (lookupTable[currentIndex][capacity] != 0)
return lookupTable[currentIndex][capacity];
// recursive call after choosing the element at the currentIndex
// if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
int profit1 = 0;
if (weights[currentIndex] <= capacity)
profit1 = profits[currentIndex] + knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength,
capacity - weights[currentIndex], currentIndex + 1);
// recursive call after excluding the element at the currentIndex
int profit2 = knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, currentIndex + 1);
lookupTable[currentIndex][capacity] = Math.max(profit1, profit2);
return lookupTable[currentIndex][capacity];
}
/**
* Knap sack int.
*
* @param profits the profits
* @param profitsLength the profits length
* @param weights the weights
* @param weightsLength the weights length
* @param capacity the capacity
* @return the int
*/
public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity)
{
int lookupTable[][] = new int [profitsLength][];
for (int i = 0; i < profitsLength; i++) {
lookupTable[i] = new int[capacity + 1];
for (int j = 0; j < capacity + 1; j++)
lookupTable[i][j] = 0;
}
return knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, 0);
}
/**
* Main.
*
* @param args the args
*/
public static void main(String args[])
{
int profits[] = {1, 6, 10, 16}; // The values of the jewelry
int weights[] = {1, 2, 3, 5}; // The weight of each
System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 7, 0));
System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 6, 0));
System.out.println("Total knapsack (dynamic programming) profit ---> " + knapSack(profits, 4, weights, 4, 6));
}
}