Unbounded Knapsack and Classical Knapsack Comparison

Question

I have read two distinct problem 0-1 Knapsack Problem and Unbounded Knapsack Problem on the internet. I found that these two problems are both solved by Dynamic Programming but in two different way. If 0-1 Knapsack Problem is solved by using two dimension array, Unbounded Knapsack Problem only utilizes one dimension array.

You can read more 0-1 Knapsack Problem and Unbounded Knapsak Problem

The difference in these two problem, as I know, is that the 0-1 Knapsack Problem only contains the limited amount of things, while Unbounded Knapsack Problem enables to take 1 or more instances of any resource. However, I do not know why it changes the way to solve this problem? Can you give me the reason for this?

Answer 1

Table approach is simpler to explain and debug, that is why algorithm decriptions usually show such way.

Note that for 0-1 Knapsack Problem we must exclude possibility to reuse item twice. So at every step of outer loop we update previous best results using current item.

But we use only the last row of table (look at indices i and i-1), so we can diminish table size to 2 x Capacity using only current and last rows.

Moreover, we can use approach with one-dimensional array, applying a trick - to avoid reusing item, we can perform traversal in backward direction.

Python code below uses data from wiki page and shows both table and linear array implementations.

wt = [23,26,20,18,32,27,29,26,30,27]
val = [505,352,458,220,354,414,498,545,473,543]

def knap1(w,v, cap):
    n = len(w)
    m = [[0]*(cap+1) for _ in range(n)]
    for i in range(n):
        for j in range(cap + 1):
            if w[i] > j:
                m[i][j] = m[i-1][j]
            else:
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i])
    return m[n-1][cap]

def knap2(w,v, cap):
    n = len(w)
    m = [0]*(cap+1)
    for i in range(n):
        for j in range(cap, w[i]-1,-1):
                m[j] = max(m[j], m[j-w[i]] + v[i])
    return m[cap]


print(knap1(wt, val, 67))
print(knap2(wt, val, 67))

>>1270
>>1270