diff options
author | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
---|---|---|
committer | William Carroll <wpcarro@gmail.com> | 2020-01-29T14·29+0000 |
commit | fb9380ba268b3cd27372acadb87b14cc96163374 (patch) | |
tree | f65d7fc8d8726499165a0949af39afd1abc8118c /universe/data_structures_and_algorithms/cake-thief.py | |
parent | 15110e6de9f85537c7847267caa35fa068aea001 (diff) | |
parent | 8ad51b24dd8719840aac47134835ea25cfe1b0b8 (diff) |
Add 'universe/' from commit '8ad51b24dd8719840aac47134835ea25cfe1b0b8'
git-subtree-dir: universe git-subtree-mainline: 15110e6de9f85537c7847267caa35fa068aea001 git-subtree-split: 8ad51b24dd8719840aac47134835ea25cfe1b0b8
Diffstat (limited to 'universe/data_structures_and_algorithms/cake-thief.py')
-rw-r--r-- | universe/data_structures_and_algorithms/cake-thief.py | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/universe/data_structures_and_algorithms/cake-thief.py b/universe/data_structures_and_algorithms/cake-thief.py new file mode 100644 index 000000000000..9eddb34b2db3 --- /dev/null +++ b/universe/data_structures_and_algorithms/cake-thief.py @@ -0,0 +1,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) |