-
Notifications
You must be signed in to change notification settings - Fork 0
/
Worstcase.java
83 lines (68 loc) · 2.35 KB
/
Worstcase.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
package OS;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class WorstFit {
private static class Bin {
int id;
int capacity;
int occupied;
Bin(int id, int capacity) {
this.id = id;
this.capacity = capacity;
this.occupied = 0;
}
}
private static class Item {
int id;
int size;
Item(int id, int size) {
this.id = id;
this.size = size;
}
}
private static List<Bin> worstFit(List<Item> items, int binCapacity) {
List<Bin> bins = new ArrayList<>();
for (Item item : items) {
boolean itemPlaced = false;
int worstFitIndex = -1;
int worstFitRemaining = -1;
// Find the bin with the worst fit (largest remaining capacity)
for (int i = 0; i < bins.size(); i++) {
Bin bin = bins.get(i);
int remaining = bin.capacity - bin.occupied;
if (remaining >= item.size && remaining > worstFitRemaining) {
worstFitIndex = i;
worstFitRemaining = remaining;
}
}
// If a suitable bin was found, place the item in it
if (worstFitIndex != -1) {
Bin bin = bins.get(worstFitIndex);
bin.occupied += item.size;
itemPlaced = true;
}
// If the item couldn't be placed, create a new bin and put the item in it
if (!itemPlaced) {
Bin newBin = new Bin(bins.size() + 1, binCapacity);
newBin.occupied = item.size;
bins.add(newBin);
}
}
return bins;
}
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item(1, 4));
items.add(new Item(2, 2));
items.add(new Item(3, 5));
items.add(new Item(4, 1));
items.add(new Item(5, 3));
int binCapacity = 10;
List<Bin> bins = worstFit(items, binCapacity);
// Print the result
for (Bin bin : bins) {
System.out.println("Bin " + bin.id + ": Occupied " + bin.occupied + "/" + bin.capacity);
}
}
}