-
Notifications
You must be signed in to change notification settings - Fork 0
/
KnapsackImp.java
79 lines (67 loc) · 2.53 KB
/
KnapsackImp.java
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
import java.util.Arrays;
/**
* A class that implements the fractional and discrete Knapsack algorithms
* by implementing the Knapsack interface.
* @author Bruce How (22242664)
*/
public class KnapsackImp implements Knapsack {
/**
* Private subclass which stores each Item and their respective
* densities (value/weight). This class implements the Comparable
* interface to compare each Item's density while keeping tracking
* of their indexes within another array.
*/
private class Item implements Comparable<Item> {
private int index;
private double density;
public Item(int index, double density) {
this.index = index;
this.density = density;
}
@Override
public int compareTo(Item item) {
return Double.compare(this.density, item.density);
}
}
@Override
public int fractionalKnapsack(int[] weights, int[] values, int capacity) {
int length = values.length;
Item densities[] = new Item[length];
for (int i = 0; i < length; i++) {
densities[i] = new Item(i, (double) values[i] / (double) weights[i]);
}
// Sort by density using the comparable method compareTo
Arrays.sort(densities);
double totalWeight = 0.0;
double totalValue = 0.0;
for (int i = length-1; i >= 0; i--) {
int j = densities[i].index;
// Check if item can fit as a whole
if (weights[j] + totalWeight <= capacity) {
totalWeight += weights[j];
totalValue += values[j];
} else { // Fit a fraction of the item
totalValue += densities[i].density * ((double) capacity - totalWeight);
break;
}
}
return (int) totalValue;
}
@Override
public int discreteKnapsack(int[] weights, int[] values, int capacity) {
int table[][] = new int[values.length+1][capacity+1];
// Construct table[][] in a bottom-up manner
for (int i = 0; i < values.length + 1; i++) {
for (int j = 0; j < capacity+1; j++) {
if (i == 0 || j == 0) {
table[i][j] = 0;
} else if (weights[i-1] <= j) {
table[i][j] = Math.max(values[i-1] + table[i-1][j-weights[i-1]], table[i-1][j]);
} else {
table[i][j] = table[i-1][j];
}
}
}
return table[values.length][capacity];
}
}