--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/python/packing.py	Sun Feb 19 12:50:51 2023 +0100
@@ -0,0 +1,60 @@
+import numpy as np
+
+def knapsack(items=[4,3,1,2], profits=[60, 50, 20, 20], capacity=7):
+    table = np.zeros((len(items)+1, capacity+1))
+    table[:, 0] = 0
+    table[0, :] = 0
+
+    for item in range(1, len(items)+1):
+        for cap in range(1, capacity+1):
+            y = 0 if items[item-1] > cap else profits[item-1]+table[item-1, cap-items[item-1]]
+            table[item, cap] = max(table[item-1, cap], y)
+
+    print(table)
+
+    # Search path
+    it, cap = len(items), capacity
+    included = [False] * len(items)
+    while it > 0:
+        if table[it-1, cap-items[it-1]] == table[it, cap] - profits[it-1]:
+            included[it-1] = True
+            cap = cap - items[it-1]
+        else:
+            included[it-1] = False
+        it -= 1
+    print(included)
+
+def binpacking(items=[1,5,5,2,4], profits=[4, 3, 2, 5, 1], capacity=5, bins=3):
+    # Each bin is capacity+1 wide: one slot for "zero capacity" and then up to capacity.
+    table = np.zeros((len(items)+1, bins*(capacity + 1)))
+    table[:, 0] = 0
+    table[0, :] = 0
+
+    # Start with first bin:
+    for item in range(1, len(items)+1):
+        if items[item-1] > capacity:
+            # Cannot pack this item; too large
+            table[item, :] = table[item-1, :]
+            continue
+        for cap in range(1, bins * (capacity + 1)):
+            # Current bin is cap//(capacity+1).
+            if (cap - items[item-1]) // (capacity+1) == cap // (capacity+1) and (cap - items[item-1]) >= 0:
+                # Fits current bin: we can pack
+                table[item, cap] = max(table[item-1, cap],  # no pack item
+                                       profits[item-1] + table[item-1, cap - items[item-1]])
+            elif cap % capacity == 0:
+                table[item, cap] = table[item, cap-1]
+            else:
+                table[item, cap] = max(table[item-1, cap], table[item, cap-1])
+
+    print(table)
+
+    included = [False] * len(items)
+    it, cap = len(items), (capacity+1) * bins - 1
+    while it > 0:
+        if table[it-1, cap-items[it-1]] == table[it, cap] - profits[it-1]:
+            included[it-1] = True
+            cap = cap - items[it-1]
+        else:
+            included[it-1] = False
+        it -= 1