unbounded knapsack

Suppose I have infinite copies of all items, what’s the most valuable way to fill the knapsack?

DP, with subproblems containing smaller knapsack. K[x] = max_i { K[x-wi] + vi }

def solve():
    dp[0] = 0
    sol[0] = []

    for x in 1 ... knapsack_size:
        dp[x] = 0

        for i in 1 ... num_items:
            if weight(i) <= x:
                # why max base case instead of incrementally adding stuff?
                # a bigger knapsack that fits 2 things can be find a sa
                dp[x] = max(dp[x], dp[x-weight(i)]+value(i))
                if dp[x] changed:
                    sol[x] = sol[x-weight(i)] + [i]

0/1 knapsack

Suppose I have one copy of each item; what’s the most valuable way to fill the knapsack? We have to keep track of a 2D DP table. Casework:

• optimal solution for j items doesn’t use item j: K[x,j] = K[x,j-1]
• optimal solution for j items does use item j: K[x,j] = K[x-weight(j),j-1]+value(j)

So we have: K[x,j] = max(K[x,j-1], K[x-weight(j),j-1]+value(j), for each j). We can thus solve 0/1 knapsack in \(O\qty(nW)\).