-
Notifications
You must be signed in to change notification settings - Fork 0
/
knapsack.py
61 lines (58 loc) · 2.85 KB
/
knapsack.py
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
# Unbounded knapsack solver (allowing for repetition of items)
# Instead of using the solver superclass, this algorithm uses a greedy approach and iteratively improves solutions using an upper bound.
# This solver will not correctly handle negative values or weights.
# Designed to run well on large knapsacks
class KnapsackItem:
def __init__(self, value, size):
self.value = value
self.size = size
self.value_ratio = value / size
class KnapsackSolver:
def solve(self, values, sizes, knapsack_size):
items = [KnapsackItem(value, size) for value, size in zip(values, sizes)]
items.sort(key=lambda item: item.value_ratio, reverse=True)
knapsack = [ 0 for item in items ]
total_value = 0
total_space = knapsack_size
best_value = 0
best_knapsack = knapsack[:]
current_item = 0
while True:
#Check upper bound
if current_item >= len(items) or total_value + total_space * items[current_item].value_ratio < best_value:
current_item -= 1
if knapsack[current_item] > 0:
#Remove all of previous item
total_value -= knapsack[current_item] * items[current_item].value
total_space += knapsack[current_item] * items[current_item].size
knapsack[current_item] = 0
#Remove one item
while knapsack[current_item] == 0:
if current_item == 0:
#Finished
print("Best knapsack (W" + str(knapsack_size) + "): " + str(sorted([("$" + str(items[i].value) + "-W" + str(items[i].size), amount) for i, amount in enumerate(best_knapsack)], key=lambda point: point[0])))
print("Total Value: $" + str(best_value))
return
current_item -= 1
total_value -= items[current_item].value
total_space += items[current_item].size
knapsack[current_item] -= 1
current_item += 1
continue
#Fill with the item
add_amount = total_space // items[current_item].size
if add_amount == 0:
current_item += 1
continue
knapsack[current_item] += add_amount
total_value += add_amount * items[current_item].value
total_space %= items[current_item].size
#Check value
if total_value > best_value:
best_value = total_value
best_knapsack = knapsack[:]
KnapsackSolver().solve([1, 30], [1, 50], 100)
KnapsackSolver().solve([1, 60], [1, 55], 100)
KnapsackSolver().solve([10, 40, 50, 70], [1, 3, 4, 5], 8123)
KnapsackSolver().solve([7, 5, 2], [6, 5, 3], 155554)
KnapsackSolver().solve([4, 2, 2, 1, 10], [12, 2, 1, 1, 4], 15000071)