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)