Skip to content

Knapsack#

 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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from dp import DPArray
from dp._visualizer import Visualizer


# An item is a 2-tuple with (space, value)
# items is a list of items in the problem instance.
def knapsack(items, capacity):
    # Initialize DPArray
    OPT = DPArray((len(items) + 1, capacity + 1), array_name="Knapsack")
    DP_items = DPArray(shape=len(items), array_name="Items", logger=OPT.logger)
    for i in range(len(items)):
        DP_items[i] = i

    # Put in base cases
    OPT[0, :] = 0
    OPT[:, 0] = 0
    # Recurrence: OPT(i, C) = max(OPT(i-1, C), OPT(i-1, C-i.space) + i.val)
    for idx in range(len(items) + 1):
        for rem in range(capacity + 1):
            # Base case: 0 value if there are no items left or if there is no space.
            if idx == 0 or rem == 0:
                continue
            # Normal case: There is an item to add and space remaining
            item = items[idx - 1]
            if idx >= 1 and rem - item[0] >= 0:
                _ = DP_items[idx - 1]
                # OPT[idx, rem] = max(OPT[idx - 1, rem], OPT[idx - 1, rem-item[0]] + item[1])
                indices = [
                    (idx - 1, rem),
                    (idx - 1, rem - item[0]),
                ]
                elements = [
                    OPT[idx - 1, rem],
                    OPT[idx - 1, rem - item[0]] + item[1],
                ]
                OPT[idx, rem] = OPT.max(indices=indices, elements=elements)
                OPT.annotate(f"Comparing: max({indices[0]}, {indices[1]})")
            # Edge case: adding item is not possible
            elif idx >= 1 and rem - item[0] < 0:
                _ = DP_items[idx - 1]
                OPT[idx, rem] = OPT[idx - 1, rem]
                OPT.annotate("Item does not fit in remaining capacity.")

    # Make a copy of data in OPT to prevent visualization of future operations.
    arr = OPT.arr

    # Recover a traceback path.
    current = (arr.shape[0] - 1, arr.shape[1] - 1)
    path = [current]
    solution = []  # List of items.

    # While the path is not fully constructed.
    while current[0] != 0 and current[1] != 0:
        i, rem = current
        capacity, value = items[i - 1]

        # Find the predecessor of current.
        # Case 1: adding item is possible and more optimal
        if (rem - capacity >= 0 and
                arr[i - 1, rem] < arr[i - 1, rem - capacity] + value):
            current = (i - 1, rem - capacity)
            path.append(current)
            solution.append(i)

        # Case 2: there is no capacity for item or not adding item is more optimal
        else:
            current = (i - 1, rem)
            path.append(current)

    path = path[::-1]
    solution = solution[::-1]
    OPT.add_traceback_path(path)

    # Define labels.
    row_labels = ["No item"]
    row_labels += [f"Item {i}: {item}" for i, item in enumerate(items, start=1)]
    column_labels = [f"Capacity {i}" for i in range(max_capacity + 1)]
    description = "Recurrence: $OPT(i, C) = \\max(OPT(i-1, C), OPT(i-1, C-c(i)) + v(i))$"

    # Visualize with the items array
    visualizer = Visualizer()
    visualizer.add_array(OPT,
                         row_labels=row_labels,
                         column_labels=column_labels,
                         description=description)
    item_col_labels = [f"Item {i}: {item}" for i, item in enumerate(items, start=1)]
    visualizer.add_array(DP_items,
                         row_labels=" ",
                         column_labels=item_col_labels)
    visualizer.show()


if __name__ == "__main__":
    items = [(2, 4), (4, 3), (7, 12), (5, 6), (13, 13)]
    max_capacity = 14
    knapsack(items, max_capacity)