K-Optimal Greedy Heuristic
The greedy algorithm follows the problem-solving heuristic of making the locally optimal choice at each stage. A greedy strategy does not always produce an optimal solution. Still, a greedy heuristic may give an optimal solution.
We start by assuming a problem scenario, where we are packing things for a trek; we aim to pack items that are helpful for the hike and also to try to keep our knapsack as light as possible because hiking with lighter luggage is more fun!😛
Here, we place ‘K’ objects into our sack irrespective of everything and add remaining items into the sack in descending order of Pᵢ/Wᵢ ratio.
If object is placed into the sack our vector takes magnitude ‘1’ else ‘0’,
Ex. If object ‘A’ and ‘D’ are put into the sack then our vector is
v = [1,0,0,1]
K takes the integral values ranging between ‘0’ and ’n’ where ’n’ is total number of items.
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Case 1 :
When K = 0, No object is placed first we fill it in descending order of Pᵢ/Wᵢ ratio, So now we start filling the knapsack with highest (Pᵢ/Wᵢ) which is ‘A’ so we add ‘A’,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 60–20 = 40
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘D’ , but we cant add ‘D’ because remaining capacity is less than weight of ‘D’
So, the object with next highest Pᵢ/Wᵢ ratio is ‘B’ so we add ‘B’,
After adding B into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
Capacity = 40–30 = 10
Since, there are no more objects lesser than the capacity we stop adding and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Case 2 :
When K = 1, We will have four sub-cases,
- Sub-case 1: Placing ‘A’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘B’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘C’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
- Sub-case 2: Placing ‘D’ into the sack and then placing remaning objects based on descending order of Pᵢ/Wᵢ ratio.
Sub-case 1:
We start by adding ‘A’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–20 = 40
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘D’ , but we cant add ‘D’ because remaining capacity is less than weight of ‘D’
So, the object with next highest Pᵢ/Wᵢ ratio is ‘B’ so we add ‘B’,
After adding B into the sack,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 40–30 = 10
Since, there are no more objects lesser than the capacity we stop adding and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Sub-case 2:
We start by adding ‘B’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–30 = 30
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘A’ , we add ‘A’ into the sack,
Capacity = 30–20 = 10
Since there are no more objects lesser than the capacity, we stop adding, and we end packing,
Now we have,
{B , A} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 30 + 20=50
Profit/Priority Score (ΣPᵢ) = 80 + 70= 150
v = [1,1,0,0]
Sub-case 3:
We start by adding ‘C’ into the sack irrespective of all other factors,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–40 = 20
Now, the object with next highest Pᵢ/Wᵢ ratio is ‘A’ , we add ‘A’ into the sack,
Capacity = 20–20 = 0
Since there are no more space left, we stop adding, and we end packing,
Now we have,
{C , A} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 40 + 20= 60
Profit/Priority Score (ΣPᵢ) = 90 + 70 = 160
v = [1,0,1,0]
Sub-case 4:
We try to add ‘D’ into the sack irrespective of all other factors, but the weight of ‘D’ is more than the sack’s capacity, so we can’t add ‘D.’
So, this sub-case is infeasible to proceed further.
Case 3:
When K = 2, We first place two objects into the sack irrespective of all other factors, and then we try to place the remaining objects in descending order of Pᵢ/Wᵢ ratio,
All the possible sets of two elements are,
(A,A),(A,B),(A,C),(A,D),(B,A),(B,B),(B,C),(B,D),(C,A),(C,B),(C,C),(C,D),(D,A),(D,B),(D,C),(D,D)
Removing the duplicates and the sets who’s weight sum is more than 60, we end up with,
(A,B),(A,C)
Sub-case 1: (A,B)
We start by adding ‘A’ and ‘B’ into the sack irrespective of all other factors,
After adding ‘A’ and ‘B’,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–(20+30) = 10
Since there are no more objects lesser than the capacity, we stop adding, and we end packing,
Now we have,
{A,B} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 20 + 30 =50
Profit/Priority Score (ΣPᵢ) = 70 + 80 = 150
v = [1,1,0,0]
Sub-case 2: (A,C)
We start by adding ‘A’ and ‘C’ into the sack irrespective of all other factors,
After adding ‘A’ and ‘C’,
Capacity = (Remaining Capacity)-(Weight of the object added)
O ={A,B,C,D}
W={20,30,40,70}
P={70,80,90,200}
Pᵢ/Wᵢ = {3.5,2.6,2.2,2.8}
C = 60
Capacity = 60–(20+40) = 0
Since there is no more space left, we stop adding, and we end packing,
Now we have,
{A , C} in our sack
Weight of Knapsack at the end (ΣWᵢ) = 40 + 20= 60
Profit/Priority Score (ΣPᵢ) = 90 + 70 = 160
v = [1,0,1,0]
Case 4:
When, K=3 we must add three objects into the sack irrespective of all other factors, but the sum of any three objects exceeds the sack’s capacity, so we stop here because K cannot take any values greater than or equal to 3.
#include <bits/stdc++.h>using namespace std;int maxindex(int* dist, int n){int mi = 0;for (int i = 0; i < n; i++) {if (dist[i] > dist[mi])mi = i;}return mi;}void selectKcities(int n, int weights[4][4], int k){int* dist = new int[n];vector<int> centers;for (int i = 0; i < n; i++) {dist[i] = INT_MAX;}int max = 0;for (int i = 0; i < k; i++) {centers.push_back(max);for (int j = 0; j < n; j++) {dist[j] = min(dist[j], weights[max][j]);}max = maxindex(dist, n);}cout << endl << dist[max] << endl;for (int i = 0; i < centers.size(); i++) {cout << centers[i] << " ";}cout << endl;}int main(){int n = 4;int weights[4][4] = { { 0, 4, 8, 5 },{ 4, 0, 10, 7 },{ 8, 10, 0, 9 },{ 5, 7, 9, 0 } };int k = 2;selectKcities(n, weights, k);}// Contributed by Balu Nagar
