Knapsack Problem

When given a set of items, where each item has a weight and a value, we need to determine a subset of items that are to be included in a collection in such a way that the total weight aggregates up to be lower than or equal to a given limit and the total value could be as big as possible. 

The Knapsack problem is an instance of a Combinatorial Optimization problem. One general approach to crack difficult problems is to identify the most restrictive constraint. For this, we must ignore the others and solve a knapsack problem, and finally, we must somehow fit the solution to satisfy the constraints that are ignored. 

Applications

For multiple cases of resource allocation problems that have some specific constraints, the problem can be solved in a way that is similar to the Knapsack problem. Following are a set of examples. 

•  Finding the least wasteful way to cut down the basic materials 
•  portfolio optimization 
•  Cutting stock problems 

Problem Scenario

Consider a problem scenario where a thief is robbing a store and his knapsack ( bag) can carry a maximal weight of W. Consider that there are n items in the store and the weight of the ith item is wi and its respective profit is pi. 

What are all the items the thief should take? 

Here, the main goal/objective of the thief is to maximize the profit anyhow. So, the items should opt-in such a way that the items which are carried by the thief will fetch the maximum profit. 

Based on the nature of the items, Knapsack problems are classified into two categories 

• Fractional Knapsack 
• Knapsack 

Fractional Knapsack

In this category, items can be broken into smaller pieces, and the thief can select fractions of items.

According to the problem scenario,

• There are n items in the store
• Weight of ith item 
• wi>0
• Profit for ith item 
• pi>0 and
• The capacity of the Knapsack is W

As the name suggests, in the Knapsack problem, items can be broken into smaller fragments. So, the thief might only take a fraction or a part of xi of ith item.

0⩽xi⩽1

The ith item in the store contributes a weight of xi.wi to the total weight in the knapsack(bag) and profit xi.pi to the Total Profit.

Hence, the main objective of the algorithm is basically to maximize the value of ∑n=1n(xi.pi) with respect to the given constraint,

∑n=1n(xi. wi)⩽W

We already know that a solution that is said to be an optimal solution must fill the knapsack(bag) exactly, if not, we could at least add a smaller fraction of one of the remaining items. This will result in an increase in the overall profit.

Thus, an optimal solution to this problem can be obtained by,

∑n=1n(xi.wi)=W

Now, we have to sort all those items based on their values of piwi, so that

pi+1wi+1 ≤ piwi

Here,  x is an array that is used to store the fraction of items.

Analysis

Suppose that we are provided with items that have already been sorted in the decreasing order of piwi, then the time taken by the “while” will be O(n). So, the total time including that includes even sorting will be O(n logn).

Example

Let us consider that the capacity of the knapsack(bag) W = 60 and the list of items are shown in the following table −

We can see that the provided items are not sorted based on the value of piwi, we perform sorting. After sorting, the items are shown in the following table.

Solution

Once we sort all the items according to the piwi, we choose all of B as the weight of B is less compared to that of the capacity of the knapsack. Further, we choose item A, as the available capacity of the knapsack is greater than the weight of A. Now, we will choose C as the next item. Anyhow, the whole item cannot be chosen as the remaining capacity of the knapsack is less than the weight of the chosen item – C.

Hence, a fraction of C (i.e. (60 − 50)/20) is chosen.

Now, we reach the stage where the capacity of the Knapsack is equal to the chosen items. Hence, no more items can be selected.

The total weight of the chosen items is 40 + 10 + 20 * (10/20) = 60

And the total profit is 101 + 281 + 121 * (10/20) = 380 + 60 = 440

This is the optimal solution. We cannot gain more profit compared to this by selecting any different combination of items out of the provided items.

Algorithm: 

Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if (weight + w[i]) ≤ W then,
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x