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
 97
 98
 99
100
101
102
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)

    return visualizer.create_app()

items = [(2, 4), (4, 3), (7, 12), (5, 6), (13, 13)]
max_capacity = 14

app = knapsack(items, max_capacity)
server = app.server

if __name__ == "__main__":
    app.run_server(debug=True, use_reloader=True)