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
|
import unittest
from math import floor
################################################################################
# Solution
################################################################################
def max_duffel_bag_value(xs, cap):
ct = (cap + 1)
maxes = [0] * ct
for c in range(cap + 1):
for w, v in xs:
if w == 0 and v > 0:
return float('inf')
if w == c:
maxes[c:] = [max(maxes[c], v)] * (ct - c)
elif w < c:
d = c - w
maxes[c:] = [max(maxes[c], v + maxes[d])] * (ct - c)
else:
continue
return maxes[cap]
################################################################################
# Tests
################################################################################
class Test(unittest.TestCase):
def test_one_cake(self):
actual = max_duffel_bag_value([(2, 1)], 9)
expected = 4
self.assertEqual(actual, expected)
def test_two_cakes(self):
actual = max_duffel_bag_value([(4, 4), (5, 5)], 9)
expected = 9
self.assertEqual(actual, expected)
def test_only_take_less_valuable_cake(self):
actual = max_duffel_bag_value([(4, 4), (5, 5)], 12)
expected = 12
self.assertEqual(actual, expected)
def test_lots_of_cakes(self):
actual = max_duffel_bag_value([(2, 3), (3, 6), (5, 1), (6, 1), (7, 1),
(8, 1)], 7)
expected = 12
self.assertEqual(actual, expected)
def test_value_to_weight_ratio_is_not_optimal(self):
actual = max_duffel_bag_value([(51, 52), (50, 50)], 100)
expected = 100
self.assertEqual(actual, expected)
def test_zero_capacity(self):
actual = max_duffel_bag_value([(1, 2)], 0)
expected = 0
self.assertEqual(actual, expected)
def test_cake_with_zero_value_and_weight(self):
actual = max_duffel_bag_value([(0, 0), (2, 1)], 7)
expected = 3
self.assertEqual(actual, expected)
def test_cake_with_non_zero_value_and_zero_weight(self):
actual = max_duffel_bag_value([(0, 5)], 5)
expected = float('inf')
self.assertEqual(actual, expected)
unittest.main(verbosity=2)
|
