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
|
from math import floor
def print_table(table):
print('\n-- TABLE --')
for row in range(len(table)):
x = ''
for col in range(len(table[row])):
x += ' ' + str(table[row][col])
print(x)
def leftover(capacity, kg):
n = floor(capacity / kg)
return n, capacity - (n * kg)
def init_table(num_rows, num_cols):
table = []
for _ in range(num_rows):
row = []
for _ in range(num_cols):
row.append(0)
table.append(row)
return table
def get(table, row, col):
if row < 0 or col < 0:
return 0
return table[row][col]
def max_haul(items, capacity):
table = init_table(len(items), capacity)
for row in range(len(table)):
for col in range(len(table[row])):
curr_capacity = col + 1
kg, val = items[row]
# A
a = get(table, row - 1, col)
# B
n, lo = leftover(curr_capacity, kg)
b = (val * n) + get(table, row - 1, lo - 1)
# commit
if kg > curr_capacity:
table[row][col] = a
else:
print(n, lo)
table[row][col] = max([a, b])
print_table(table)
return table[-1][-1]
# There are multiple variants of this problem:
# 1. We're allowed to take multiple of each item.
# 2. We can only take one of each item.
# 3. We can only take a fixed amount of each item.
items = [(7,160), (3,90), (2,15)]
capacity = 20
result = max_haul(items, capacity)
expected = None
print("Result: {} == Expected: {}".format(result, expected))
assert result == expected
print("Success!")
|
