/
package_optimizer.go
100 lines (87 loc) · 2.62 KB
/
package_optimizer.go
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
package services
import (
"math"
)
type packOptimizer struct {
packSizes []int
order int
}
func newPackOptimizer(packSizes []int, order int) *packOptimizer {
return &packOptimizer{
packSizes: packSizes,
order: order,
}
}
func (p *packOptimizer) findOptimalPacks(order int, packSizes []int, currentSolution []int) []int {
if order == 0 {
return currentSolution
}
if order < 0 || len(packSizes) == 0 {
return nil
}
withCurrentPack := p.findOptimalPacks(order-packSizes[0], packSizes, append(currentSolution, packSizes[0]))
withoutCurrentPack := p.findOptimalPacks(order, packSizes[1:], currentSolution)
if withCurrentPack == nil {
return withoutCurrentPack
} else if withoutCurrentPack == nil {
return withCurrentPack
} else {
if len(withCurrentPack) <= len(withoutCurrentPack) {
return withCurrentPack
} else {
return withoutCurrentPack
}
}
}
// PackSplitter represents an instance of the package splitting algorithm
type PackSplitter struct {
packSizes []int
order int
}
// NewPackSplitter creates a new PackSplitter instance
func NewPackSplitter(packSizes []int, order int) *PackSplitter {
return &PackSplitter{
packSizes: packSizes,
order: order,
}
}
func (p *PackSplitter) minimumRemaining() int {
result := int(math.Ceil(float64(p.order) / float64(p.packSizes[0])))
minRemain := result*p.packSizes[0] - p.order
for i := 1; i < len(p.packSizes); i++ {
result = int(math.Ceil(float64(p.order) / float64(p.packSizes[i])))
remain := result*p.packSizes[i] - p.order
if minRemain > remain {
minRemain = remain
}
}
return minRemain
}
func (p *PackSplitter) splitOrderIntoPacksArray() []int {
minRemainining := p.minimumRemaining()
var bestOptimalSolution []int
for i := 0; i < minRemainining+1; i++ {
exceededOrder := p.order + i
packOptimizer := newPackOptimizer(p.packSizes, exceededOrder)
solution := packOptimizer.findOptimalPacks(packOptimizer.order, packOptimizer.packSizes, []int{})
if solution != nil {
bestOptimalSolution = solution
break
}
}
return bestOptimalSolution
}
func countPackAmountsFromResultArray(result []int) map[int]int {
//Create a dictionary of values for each element
packSizesWithAmounts := make(map[int]int)
for _, packSize := range result {
packSizesWithAmounts[packSize] = packSizesWithAmounts[packSize] + 1
}
return packSizesWithAmounts
}
// SplitOrderIntoPacks splits the order amount into packs using PackSplitter.packSizes
func (p *PackSplitter) SplitOrderIntoPacks() map[int]int {
packSizesArray := p.splitOrderIntoPacksArray()
packSizesWithAmount := countPackAmountsFromResultArray(packSizesArray)
return packSizesWithAmount
}