Imaginary situation: “There was a theft at someplace and the police are investigating the incident.” No, I am not writing any news article. Let me make a reference to the thief. There are a lot of valuable objects to steal and unfortunately, the thief has only a sack that is capable of particular, say 15 kg, to carry out the objects. How does he choose the objects to carry with him? What are his choices in taking the decision? Let’s look into details.

There are two methods in Knapsack problem:

1. Fractional knapsack problem
2. 0-1 Knapsack problem

Fractional Knapsack problem:

It is one of the combinatorial optimization algorithms. Given a set of weights and values of n objects, and we should fill them in the knapsack of the given weight, say W, to achieve maximum profit/value. Here we use the Greedy approach to get an efficient solution. The objects can be divided into parts to get maximum value. This is why it was named Fractional Knapsack problem meaning the objects can be partitioned.

Algorithm:

1. Calculate the Value/weight ratio. Table 1.
2. Arrange them in ascending order or in the descending order (recommended) according to the ratio. Table 2.
3. Now choose the one with the highest value/weight ratio. Calculate the total value by adding the values of chosen descending order ratios. Parallelly, subtract the weight of the selected ratio from the available weight. This will be more clear when you see the table below. Table 3.
4. The final value remained when the weight is zero will be our required solution.

Note:

1. When you encounter the weight less than the weight of the object, take the partial weight from the weight of the object such that the value corresponds to the weight taken from the total weight. Let’s clarify this with an example.
2. While arranging in the descending or ascending order, if ratios are same the arrangement can be done in either ways.

The total weight [W] given is 15 units.

Object No.	Value/Profit	Weight[wi]	Value/Weight Ratio
1	10	2	5
2	6	3	2
3	18	6	3
4	2	2	1
5	6	1	6
6	16	4	4
7	3	1	3

Object No.	Value	Value/Weight Ratio	Corresponding Weights
5	6	6	1
1	10	5	2
6	16	4	4
3	18	3	6
7	3	3	1
2	6	2	3
4	2	1	2

Object No.	Chosen Ratio	Weight Remained[W-wi]	Total Value
5	6	15-1=14	6
1	5	14-2=12	10+6=16
6	4	12-4=8	16+16=32
3	3	8-6=2	32+18=50
7	3	2-1=1	50+3=53
2	*2	1-1=0	53+2=55

*———> Denotes that the partial weight is taken. In the above case, the weight remained before reaching the ratio is “1” but the weight of the object is 3. So the corresponding value i.e, for weight of 1 unit the value is 2. Since the weight remained to get filled in the sack is 1 only value of 2 is taken.

Hence the solution for our thief was found out. If he includes the objects with numbers 5, 1, 6, 3, 7 and partial weight of 2, the maximum profit can be achieved.

Some of the applications of Knapsack problem:

1. Maximizing customer values within given supply capacity.
2. Solving production planning problem. Why?
3. Network selection: Maximum frequency
4. Optimization for content delivery Networks.

Practice Problems:

Item	A	B	C	D
Profit/Value	280	100	120	120
Weight	40	10	20	24

Object	Weight	Values
I1	5	30
I2	10	20
I3	20	100
I4	30	90
I5	40	160

Stay tuned for more! If unclear feel free to contact us or comment down!

Additional Algorithms:

1. Prim’s Algorithm
2. Kruskal’s Algorithm
3. Huffman Coding
4. Dynamic Programming
5. 0/1 Knapsack Problem
6. Combinatorial Optimization