-
Notifications
You must be signed in to change notification settings - Fork 4
/
Greedy.java
127 lines (102 loc) · 3.96 KB
/
Greedy.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
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package MDiaz;/*
Class: Greedy
Author: Melany Diaz
with assistance from: Gerry Howser
Creation date: 3/5/2016
Modifications:
Date Name reason
3/10/2016 Melany Diaz Debugging
*/
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
/**
In this project you will implement three solutions to 0/1 Knapsack and compare the quality of those solutions
and the run-time cost of their solutions.
This class will implement the Greedy solution: Form a price density array, sort it in non-ascending order,
and use a greedy strategy to fit the greatest value into the knapsack.
*/
public class Greedy {
//instance variables
private static int capacity;
private static int[] prices;
private static int[] weight;
private static int numItems;
private static int maxValue;
private static int currentWeight;
//rearranged weight array
public static int[] orderedWeights;
//Constructors
public Greedy(int capacity, int[] prices, int[] weight, int numItems)
{
this.capacity = capacity;
this.numItems = numItems;
this.prices = prices;
this.weight = weight;
this.orderedWeights = new int[numItems];
}
// Methods
/**
* finds the solution to the 0/1 knapsack problem
*
* Pre-condition: Array has a length > 0, the integers in the price and weight array are positive, and the
* prices array has the same number of items as the weights array
*
* Post condition: The return value is the max value with the capacity allotted.
**/
public static int greedy(int capacity, int[] prices, int[] weight, int numItems) {
//checking preconditions
assert (numItems > 0);
assert (prices.length == weight.length);
for (int i = 0; i < numItems; i++){
assert (prices[i] >= 0);
assert (weight[i] >= 0);
}
//sort price list in non-ascending order
HeapSort h = new HeapSort();
int[] OGPrices = Arrays.copyOf(prices, numItems);
h.heapSort(prices);
// System.out.println(Arrays.toString(prices));
//rearrange weight list accordingly
orderedWeights = newWeights(prices, OGPrices, weight, numItems);
// System.out.println(Arrays.toString(orderedWeights));
//fill the knapsack using the greedy idea
currentWeight = 0;
int w =0;
while(currentWeight <= capacity && w < numItems){
if(orderedWeights[w] <= (capacity - currentWeight)) {
// System.out.print(prices[w] + " ");
currentWeight += orderedWeights[w];
maxValue += prices[w];
}
w++;
}
return maxValue;
}
//used to rearrange weight array to match new, ordered, price array
public static int[] newWeights(int[] newPrices, int[] OGPrices, int[] weight, int numItems){
for(int j = 0; j < numItems; j++){
int i = 0;
boolean found = false;
while (!found && i <numItems){
if(newPrices[j] == OGPrices[i]){
OGPrices [i] = Integer.MAX_VALUE;
orderedWeights[j] = weight[i];
found = true;
}
i++;
}
}
return orderedWeights;
}
//used to time how long it takes to find the solution using greedy algorithm
//returns the value of the knapscack stolen
public long TimeToFind(int capacity, int[] prices, int[] weight, int numItems){
long start = System.nanoTime();
int value = greedy(capacity, prices, weight, numItems);
long end = System.nanoTime();
long duration = end- start;
System.out.println("value for greedy algorithm: " + value);
return duration;
}
}