Knapsack Problem

Posted on In

Knapsack Problem

Knapsack problem is a constraint optimization problem. You have to find an optimal answer given certain constraints (capacity of knapsack). There are 3 different variants: 0-1 knapsack, fractional knapsack and unbounded knapsack. We will discuss them one by one.

0-1 Knapsack Problem

What is a 0-1 Knapsack Problem?

In the 0-1 knapsack problem, we can either keep an item or not. There is no way to split an item. Each item has a value and a weight. The knapsack, or the bag, has a weight capacity. Our target is to fill the bag with maximum value while not exceeding its capacity.

Input: bag weight capacity \(W\), \(n\) items with value value[] and weight weight[].

Output: maximum feasible value

Let' try robust methods

For knapsack problem, greedy algorithm does not work, we will not discuss the details about the greedy algorithm in this article. Please refer to this article.

A basic idea is to search all possible subsets. We starts with an empty bag and put items one by one. The initial state of this bag is 0 value and \(W\) remaining capacity. Now we pick the first item. Value of the first item is value[0] and weight of it is weight[0]. If the bag can hold this item, namely weight[0] <= W, we put it in and update the status of bag to value = value[0], remaining capacity = W - weight[0]. If the bag cannot hold this item, namely weight[0] > W, just skip this item. Continue adding new items until all items are used up or the capacity of the bag is used up.

1
2
3
4
5
6
7
8
9
10
11
def KnapsackProblem(W:int, itemIndex:int, weight:list, value:list):
    # if all items or used up or the capacity of bag is used up, return
    if itemIndex >= len(weight) or W <= 0:
        return 0
    # add new item
    if weight[itemIndex] > W:
        # skip this item
        return KnapsackProblem(W, itemIndex + 1, weight, value)
    else:
        # recursion
        return max(KnapsackProblem(W, itemIndex + 1, weight, value), KnapsackProblem(W - weight[itemIndex], itemIndex + 1, weight, value) + value[itemIndex])

The algorithm above works pretty well, but there is one big problem: we do a lot repeated calculation which will significantly increase time consumption. For each item, we have to consider 2 cases, either this item is included or not. So the time complexity is \(O(2^n)\).

Trade-off: time or space

In order to solve such overlapping subproblems, we can use dynamic programming. The basic idea of it is to use additional space to memorize repeated results so that the search process can be speed up.

A good way to reduce the repeated calculation is to store the results of intermediate subproblems in an array o vector. DP[n][W] will store the optimal results with the first n items and the bag with W capacity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DP = [[-1 for _ in range(W + 1)] for _ in range(len(weight) + 1)]
def KnapsackProblem(W:int, itemIndex:int, weight:list, value:list):
    # if all items or used up or the capacity of bag is used up, return
    if itemIndex >= len(weight) or W <= 0:
        return 0
    
    # check existing DP data
    if DP[itemIndex][W] != -1:
        return DP[itemIndex][W]
    
    # add new item
    if weight[itemIndex] > W:
        # skip this item
        DP[itemIndex][W] = KnapsackProblem(W, itemIndex + 1, weight, value)
    else:
        # recursion
        DP[itemIndex][W] = max(KnapsackProblem(W, itemIndex + 1, weight, value), KnapsackProblem(W - weight[itemIndex], itemIndex + 1, weight, value) + value[itemIndex])
    
    return DP[itemIndex][W]

Since the index of a list starts from 0 in python, the size of DP is \((W+1)*(n+1)\). All we need to do is to fill the matrix, DP. Thus the time complexity is \(O(n*W)\) and the space complexity is also \(O(n*W)\).

You may notice that: actually we do not need to memorize all intermediate results and what really matters is just the optimal result for different bag capacity. When we consider the \(i^{th}\) , we do not need to consider

1
2
3
4
5
6
7
8
9
10
DP = [-1 for _ in range(W+1)]
def KnapsackProblem(W:int, itemIndex:int, weight:list, value:list):
    if itemIndex >= len(weight) or W <= 0:
        return 0
    
    if weight[itemIndex] > W:
        return KnapsackProblem(W, itemIndex+1, weight, value)
    else:
        DP[W] = max(KnapsackProblem(W, itemIndex+1, weight, value), KnapsackProblem(W-weight[itemIndex], itemIndex+1, weight, value)+value[itemIndex])
        return DP[W]

The optimized method has \(O(n * W)\) time complexity and \(O(W)\) space complexity.

Take-away

The key of dynamic programming is to trade space for time. Through memorizing overlapping intermediate results, the algorithm is speed up.

Fractional Knapsack Problem

What is Fractional Knapsack Problem?

The only difference between 0-1 knapsack problem and fractional knapsack problem is that we can break items to fill the bag. Thus we can use greedy approach. We always prefer the item with the largest \(value/weight\) ratio.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def KnapsackProblem(W:int, itemIndex:int, weight:list, value:list):
    # sort items based on value/weight ratio
    itemIndex = [i for i in range(len(weight))]
    itemIndex.sort(key=lambda i: value[i] / weight[i], reverse=True)
	
    # init result
    ans = 0

    # go throught all items
    for index in itemIndex:
        if weight[index] <= W:
            # add this item
            W -= weight[index]
            ans += value[index]
        else:
            # add part of this item an break
            ans += value[index] / weight[index] * W
            
    return ans

Unbounded Knapsack Problem

What is Unbounded Knapsack Problem?

The difference between unbounded knapsack problem and 0-1 knapsack problem is that: there is no limit on the number of a certain item, namely repetition of items is allowed.

Same with 0-1 Knapsack Problem?

The only part we need to modify in the algorithm is: do not update the itemIndex if we decide to pick this item (because there is no limit on the number of item); continue considering this item until this item cannot fit knapsack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
DP = [[-1 for _ in range(W + 1)] for _ in range(len(weight) + 1)]
def KnapsackProblem(W:int, itemIndex:int, weight:list, value:list):
    if itemIndex >= len(weight) or W <= 0:
        return 0
    
    # if it is the last item
    if itemIndex == len(weight) - 1:
        return W // weight[-1] * value[-1]
    
    if DP[itemIndex][W] != -1:
        return DP[itemIndex][W]
    
    if weight[itemIndex] > W:
        DP[itemIndex][W] = KnapsackProblem(W, itemIndex + 1, weight, value)
    else:
        # if we pick this item, do not itemIndex + 1, continue focusing on this item
        DP[itemIndex][W] = max(KnapsackProblem(W, itemIndex + 1, weight, value), KnapsackProblem(W - weight[itemIndex], itemIndex, weight, value) + value[itemIndex])
    
    return DP[itemIndex][W]

Time Complexity: \(O(n * W)\). Space Complexity: \(O(n * W)\).

We can also improve the space complexity (similar to what we did to the 0-1 Knapsack Problem).

1