Knapsack one of each item

In [2]:

    

from typing import List


    

In [13]:

    

# this amounts to a greedy solution, incorrect
def knapsack_one_of_each_attempt1(ws: List[int],
                         vs: List[int],
                         b: int) -> int:
    n = len(ws)
    k = [0] * n
    w = [0] * n
    
    k[0] = vs[0] if ws[0] <= b else 0
    w[0] = ws[0] if ws[0] <= b else 0
    for i in range(1, n):
        k[i], w[i] = max(
            (vs[i] if ws[i] <= b else 0, ws[i]),  # just the item itself
            max([
                (
                    (vs[i] if w[j] + ws[i] <= b else 0) + k[j],
                    w[j] + (ws[i] if w[j] + ws[i] <= b else 0)
                )
                for j in range(i)
            ])
        )
    
    print(w)
    print(k)
    return k[-1]


    

In [15]:

    

knapsack_one_of_each([15, 12, 10, 5], [15, 10, 8, 1], 22) == 18


    

    




[15, 15, 15, 20]
[15, 15, 15, 16]






    
Out[15]:





False

In [16]:

    

import numpy as np


    

In [21]:

    

def knapsack_one_of_each_attempt2(ws: List[int],
                         vs: List[int],
                         b: int) -> int:
    n = len(ws)
    k = np.zeros((n + 1, b + 1))
    
    for i in range(1, n + 1):
        for b in range(1, b + 1):
            if ws[i - 1] <= b:
                k[i, b] = max(k[i, b - ws[i - 1]] + vs[i - 1],
                             k[i - 1, b])
            else:
                k[i, b] = k[i - 1, b]
                
    return k[n, b]


    

In [23]:

    

knapsack_one_of_each_attempt2([15, 12, 10, 5], [15, 10, 8, 1], 22)


    

    
Out[23]:





18.0