Fractional Knapsack Problem
The knapsack problem states that − given a set of items, holding weights and profit values, one must determine the subset of the items to be added in a knapsack such that, the total weight of the items must not exceed the limit of the knapsack and its total profit value is maximum.
It is one of the most popular problems that take greedy approach to be solved. It is called as the Fractional Knapsack Problem.
To explain this problem a little easier, consider a test with 12 questions, 10 marks each, out of which only 10 should be attempted to get the maximum mark of 100. The test taker now must calculate the highest profitable questions – the one that he’s confident in – to achieve the maximum mark. However, he cannot attempt all the 12 questions since there will not be any extra marks awarded for those attempted answers. This is the most basic real-world application of the knapsack problem.
Knapsack Algorithm
The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are taken as an input for the fractional knapsack algorithm and the subset of the items added in the knapsack without exceeding the limit and with maximum profit is achieved as the output.
Algorithm
Consider all the items with their weights and profits mentioned respectively.
Calculate Pi/Wi of all the items and sort the items in descending order based on their Pi/Wi values.
Without exceeding the limit, add the items into the knapsack.
If the knapsack can still store some weight, but the weights of other items exceed the limit, the fractional part of the next time can be added.
Hence, giving it the name fractional knapsack problem.
Examples
For the given set of items and the knapsack capacity of 10 kg, find the subset of the items to be added in the knapsack such that the profit is maximum.
| Items | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Weights (in kg) | 3 | 3 | 2 | 5 | 1 |
| Profits | 10 | 15 | 10 | 12 | 8 |
Solution
Step 1
Given, n = 5
Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}
Calculate Pi/Wi for all the items
| Items | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Weights (in kg) | 3 | 3 | 2 | 5 | 1 |
| Profits | 10 | 15 | 10 | 20 | 8 |
| Pi/Wi | 3.3 | 5 | 5 | 4 | 8 |
Step 2
Arrange all the items in descending order based on Pi/Wi
| Items | 5 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|---|
| Weights (in kg) | 1 | 3 | 2 | 5 | 3 |
| Profits | 8 | 15 | 10 | 20 | 10 |
| Pi/Wi | 8 | 5 | 5 | 4 | 3.3 |
Step 3
Without exceeding the knapsack capacity, insert the items in the knapsack with maximum profit.
Knapsack = {5, 2, 3}
However, the knapsack can still hold 4 kg weight, but the next item having 5 kg weight will exceed the capacity. Therefore, only 4 kg weight of the 5 kg will be added in the knapsack.
| Items | 5 | 2 | 3 | 4 | 1 |
|---|---|---|---|---|---|
| Weights (in kg) | 1 | 3 | 2 | 5 | 3 |
| Profits | 8 | 15 | 10 | 20 | 10 |
| Knapsack | 1 | 1 | 1 | 4/5 | 0 |
Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10, with maximum profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37.
Example
Following is the final implementation of Fractional Knapsack Algorithm using Greedy Approach −
#include <stdio.h>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
printf("Added object %d (%d, %d) completely in the bag. Space left: %d.
", maxi + 1, w[maxi], p[maxi], cur_w);
else {
printf("Added %d%% (%d, %d) of object %d in the bag.
", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
printf("Filled the bag with objects worth %.2f.
", tot_v);
return 0;
}
Output
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
#include <iostream>
int n = 5;
int p[10] = {3, 3, 2, 5, 1};
int w[10] = {10, 15, 10, 12, 8};
int W = 10;
int main(){
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
printf("Added object %d (%d, %d) completely in the bag. Space left: %d.
", maxi + 1, w[maxi], p[maxi], cur_w);
else {
printf("Added %d%% (%d, %d) of object %d in the bag.
", (int)((1 + (float)cur_w/p[maxi]) * 100), w[maxi], p[maxi], maxi + 1);
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
printf("Filled the bag with objects worth %.2f.
", tot_v);
return 0;
}
Output
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
public class Main {
static int n = 5;
static int p[] = {3, 3, 2, 5, 1};
static int w[] = {10, 15, 10, 12, 8};
static int W = 10;
public static void main(String args[]) {
int cur_w;
float tot_v = 0;
int i, maxi;
int used[] = new int[10];
for (i = 0; i < n; ++i)
used[i] = 0;
cur_w = W;
while (cur_w > 0) {
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)w[i]/p[i] > (float)w[maxi]/p[maxi])))
maxi = i;
used[maxi] = 1;
cur_w -= p[maxi];
tot_v += w[maxi];
if (cur_w >= 0)
System.out.println("Added object " + maxi + 1 + " (" + w[maxi] + "," + p[maxi] + ") completely in the bag. Space left: " + cur_w);
else {
System.out.println("Added " + ((int)((1 + (float)cur_w/p[maxi]) * 100)) + "% (" + w[maxi] + "," + p[maxi] + ") of object " + (maxi + 1) + " in the bag.");
tot_v -= w[maxi];
tot_v += (1 + (float)cur_w/p[maxi]) * w[maxi];
}
}
System.out.println("Filled the bag with objects worth " + tot_v);
}
}
Output
Added object 41 (8,1) completely in the bag. Space left: 9 Added object 11 (15,3) completely in the bag. Space left: 6 Added object 21 (10,2) completely in the bag. Space left: 4 Added object 01 (10,3) completely in the bag. Space left: 1 Added 19% (12,5) of object 4 in the bag. Filled the bag with objects worth 45.4
n = 5
p = [3, 3, 2, 5, 1]
w = [10, 15, 10, 12, 8]
W = 10
cur_w = W
tot_v = 0
used = [0] * 10
for i in range(n):
used[i] = 0
while cur_w > 0:
maxi = -1
for i in range(n):
if (used[i] == 0) and ((maxi == -1) or ((w[i] / p[i]) > (w[maxi] / p[maxi]))):
maxi = i
used[maxi] = 1
cur_w -= p[maxi]
tot_v += w[maxi]
if cur_w >= 0:
print(f"Added object {maxi + 1} ({w[maxi]}, {p[maxi]}) completely in the bag. Space left: {cur_w}.")
else:
percent_added = int((1 + (cur_w / p[maxi])) * 100)
print(f"Added {percent_added}% ({w[maxi]}, {p[maxi]}) of object {maxi + 1} in the bag.")
tot_v -= w[maxi]
tot_v += (1 + (cur_w / p[maxi])) * w[maxi]
print(f"Filled the bag with objects worth {tot_v:.2f}.")
Output
Added object 5 (8, 1) completely in the bag. Space left: 9. Added object 2 (15, 3) completely in the bag. Space left: 6. Added object 3 (10, 2) completely in the bag. Space left: 4. Added object 1 (10, 3) completely in the bag. Space left: 1. Added 19% (12, 5) of object 4 in the bag. Filled the bag with objects worth 45.40.
Applications
Few of the many real-world applications of the knapsack problem are −
Cutting raw materials without losing too much material
Picking through the investments and portfolios
Selecting assets of asset-backed securitization
Generating keys for the Merkle-Hellman algorithm
Cognitive Radio Networks
Power Allocation
Network selection for mobile nodes
Cooperative wireless communication
