It takes a list of cake type tuples and a weight capacity, it returns the maximum monetary value the duffel bag can hold.

maxDuffleBagValue.py

#!/usr/bin/env python3


# The function maxDuffleBagValue() takes a list of cake type tuples
# and a weight capacity, it returns the maximum monetary value
# the duffel bag can hold.
#
# items are formated are formated as (weight, value)
# cap is the weight capacity
# isUnique indicates if there are multiple of the same item
def maxDuffleBagValue(items, cap, isUnique):
    maxValues = []

    # Initilize the matrix to be all zeros
    for i in range(0, len(items)+1):
        row = []
        for j in range(0, cap+1):
            row.append(0)
        maxValues.append(row)

    for i in range(1, len(items)+1):
        weight, value = items[i-1]
        for j in range(1, cap+1):
            # New item is within the current weight limit
            if weight <= j:
                # Each item is unique
                if isUnique:
                    newValue = value + maxValues[i-1][j-weight]
                # You can have multiple of the same item
                # search for the max value of remaning weight in the same row
                else:
                    newValue = value + maxValues[i][j-weight]
                maxValues[i][j] = max(
                    maxValues[i-1][j],
                    newValue
                )
            # New item is more than the current weight limit
            else:
                maxValues[i][j] = maxValues[i-1][j]

    return maxValues[len(items)][cap]

print('Case 1:')
cake_tuples = [(7, 160), (3, 90), (2, 15)]
capacity = 20
maxValue = maxDuffleBagValue(cake_tuples, capacity, isUnique=False)
print(maxValue)
# returns 555 (6 of the middle type of cake and 1 of the last type of cake)
print('Case 2:')
cake_tuples = [(1, 1500), (4, 3000), (3, 2000)]
capacity = 4
maxValue = maxDuffleBagValue(cake_tuples, capacity, isUnique=True)
print(maxValue)
# returns 3500 (the first cake and the last cake)