Difference between 0/1 Knapsack problem and Fractional Knapsack problem

What is Knapsack Problem?

Suppose you have been given a knapsack or bag with a limited weight capacity, and each item has some weight and value. The problem here is that “Which item is to be placed in the knapsack such that the weight limit does not exceed and the total value of the items is as large as possible?”.

Consider the real-life example. Suppose there is a thief and he enters the museum. The thief contains a knapsack, or we can say a bag that has limited weight capacity. The museum contains various items of different values. The thief decides what items are should he keep in the bag so that profit would become maximum.

Some important points related to the knapsack problem are:

• It is a combinatorial optimization-related problem.
• Given a set of N items – usually numbered from 1 to N; each of these items has a mass wi and a value vi.
• It determines the number of each item to be included in a collection so that the total weight M is less than or equal to a given limit and the total value is as large as possible.
• The problem often arises in resource allocation where there are financial constraints.

Knapsack Problem Variants:

1. 0/1 knapsack problem

A knapsack means a bag. It is used for solving knapsack problems. This problem is solved by using a dynamic programming approach. In this problem, the items are either completely filled or no items are filled in a knapsack. 1 means items are completely filled or 0 means no item in the bag. For example, we have two items having weights of 12kg and 13kg, respectively. If we pick the 12kg item then we cannot pick the 10kg item from the 12kg item (because the item is not divisible); we have to pick the 12kg item completely.

• In this problem, we cannot take the fraction of the items. Here, we have to decide whether we have to take the item, i.e., x = 1 or not, i.e., x = 0.
• The greedy approach does not provide the optimal result in this problem.
• Another approach is to sort the items by cost per unit weight and starts from the highest until the knapsack is full. Still, it is not a good solution. Suppose there are N items. We have two options either we select or exclude the item. The brute force approach has O(2^N) exponential running time. Instead of using the brute force approach, we use the dynamic programming approach to obtain the optimal solution.

Pseudocode of 0/1 knapsack problem:

DP-01KNAPSACK(p[], w[], n, M) // n: number of items; M: capacity
for ̟j := 0 to M C[0, ̟ j] := 0;
for i := 0 to n C[i, 0] := 0;
for i := 1 to n
for ̟ := 1 to M
if (w[i] >j ̟) // cannot pick item i
C[i, ̟j] := C[i – 1, ̟];
else
if ( p[i] + C[i-1, ̟ – w[i]]) > C[i-1, ̟j])
C[i, j] := p[i] + C[i – 1, ̟j – w[i]];
else
C[i, j ̟] := C[i – 1, j ̟];
return C[n, M];

Time Complexity: O(N*W))
Auxiliary Space: O(N*C)

2. Fractional knapsack problem

This problem is also used for solving real-world problems. It is solved by using the Greedy approach. In this problem we can also divide the items means we can take a fractional part of the items that is why it is called the fractional knapsack problem. For example, if we have an item of 13 kg then we can pick the item of 12 kg and leave the item of 1 kg. To solve the fractional problem, we first compute the value per weight of each item.

• As we know that the fractional knapsack problem uses a fraction of the items so the greedy approach is used in this problem.
• The fractional knapsack problem can be solved by first sorting the items according to their values, and it can be done in O(NlogN) This approach starts with finding the most valuable item, and we consider the most valuable item as much as possible, so start with the highest value item denoted by v_i. Then, we consider the next item from the sorted list, and in this way, we perform the linear search in O(N) time complexity.
• Therefore, the overall running time would be O(NlogN) plus O(N) equals to O(NlogN). We can say that the fractional knapsack problem can be solved much faster than the 0/1 knapsack problem.

Pseudocode of Fractional knapsack problem:

GREEDY_FRACTIONAL_KNAPSACK(X, V, W, M)

S ← Φ   // Set of selected items, initially empty
SW ← 0    // weight of selected items
SP ← 0    // profit of selected items
i ← 1

while i ≤ n do
  if (SW + w[i]) ≤ M then
      S ← S ∪ X[i]                
      SW ← SW + W[i]
      SP ← SP + V[i]
  else
      frac ← (M – SW) / W[i]  
      S ← S ∪ X[i] * frac      // Add fraction of item X[i]
      SP ← SP + V[i] * frac    // Add fraction of profit
      SW ← SW + W[i] * frac    // Add fraction of weight
  end
  i ← i + 1
end

Time Complexity: O(NlogN)
Auxiliary Space: O(1)

Following are the differences between the 0/1 knapsack problem and the Fractional knapsack problem.