1 files changed, 42 insertions, 0 deletions
diff --git a/scratch/facebook/london-knapsack.py b/scratch/facebook/london-knapsack.py
new file mode 100644
index 000000000000..a034fb49611d
--- /dev/null
+++ b/scratch/facebook/london-knapsack.py
@@ -0,0 +1,42 @@
+from utils import get, init_table, print_table
+
+def optimal_itinerary(duration, items):
+    min_duration = min([duration for duration, _ in items])
+    max_duration = max([duration for duration, _ in items])
+    table = init_table(rows=len(items), cols=int(max_duration / min_duration), default=0)
+    to_index = lambda duration: int(duration / min_duration) - 1
+    to_duration = lambda i: i * min_duration + min_duration
+
+    for row in range(len(table)):
+        for col in range(len(table[row])):
+            curr_duration = to_duration(col)
+            duration, value = items[row]
+            if duration > curr_duration:
+                a = 0
+            else:
+                a = value + get(table, row - 1, to_index(curr_duration - duration))
+            b = get(table, row - 1, col)
+            table[row][col] = max([a, b])
+
+        print_table(table)
+    return table[-1][-1]
+
+# You're in London for two days, and you'd like to see the following
+# attractions. How can you maximize your time spent in London?
+westminster = (0.5, 7)
+globe_theater = (0.5, 6)
+national_gallery = (1, 9)
+british_museum = (2, 9)
+st_pauls_cathedral = (0.5, 8)
+items = [
+    westminster,
+    globe_theater,
+    national_gallery,
+    british_museum,
+    st_pauls_cathedral,
+]
+result = optimal_itinerary(2, items)
+expected = 24
+print(result, expected)
+assert result == expected
+print("Success!")