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