Greedy algorithms implement optimal local selections in the hope that those selections will lead to an optimal global solution for the problem to be solved. Greedy algorithms are often not too hard to set up, fast (time complexity is often a linear function or very much a second-order function). Besides, these programs are not hard to debug and use less memory. But the results are not always an optimal solution. Greedy strategies are often used to solve the combinatorial optimization problem by building an option A. Option A is constructed by selecting each component Ai of A until complete (enough n components). For each Ai, you choose Ai optimally. In this way, it is possible that at the last step you have nothing to select but to accept the last remaining value. There are two critical components of greedy decisions:
Way of greedy selection. You can select which solution is best at present and then solve the subproblem arising from making the last selection. The selection of greedy algorithms may depend on previous selections. But it cannot depend on any future selection or depending on the solutions of subproblems. The algorithm evolves in a way that makes selections in a loop, at the same time shrinking the given problem to smaller subproblems. Optimal substructure. You perform the optimal substructure for a problem if the optimal solution of this problem contains optimal solutions to its subproblems.
A greedy algorithm has five components:
A set of candidates, from which to create solutions. A selection function, to select the best candidate to add to the solution. A feasible function is used to decide if a candidate can be used to build a solution. An objective function, fixing the value of a solution or an incomplete solution. An evaluation function, indicating when you find a complete solution.
In this tutorial, you will learn
What is Greedy Strategy?
The Idea of Greedy One
The Idea of Greedy Two
The Idea of Greedy Three
Java code for Greedy Three
Python3 code for Greedy Three
C# code for Greedy Three
Counter-example of Greedy Three
The Idea of Greedy One
With the first idea, you have the following steps of Greedy One:
Sort in non-increasing order of values. In turn consider the ordered packages, put the considering package into knapsack if the remaining capacity of the knapsack is enough to contain it (which means that the total weight of the packages that have been put into the knapsack and weight of considering packages do not exceed the capacity of the knapsack).
However, this greedy algorithm does not always give the optimal solution. Here you have a counter-example:
The parameters of the problem are: n = 3; M = 19. The packages: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Great value but also great weight. The algorithm will select package 1 with a total value of 20, while the optimal solution of the problem is selected (package 2, package 3) with a total value of 24.
The Idea of Greedy Two
With the second idea, you have the following steps of Greedy Two:
Sort in non-decreasing order of weights. In turn consider the ordered packages, put the considering package into knapsack if the remaining capacity of the knapsack is enough to contain it (which means that the total weight of the packages that have been put into the knapsack and weight of considering packages do not exceed the capacity of the knapsack).
However, this greedy algorithm does not always give the optimal solution. Here you have a counter-example:
The parameters of the problem are: n = 3; M = 11. The packages: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Light weight but the value is also very light. The algorithm will select (package 1, package 2) with a total value of 26, while the optimal solution of the problem is (package 3) with a total value of 28.
The Idea of Greedy Three
With the third idea, you have the following steps of Greedy Three. In fact, this is the most widely used algorithm.
Sort packages in the order of non-increasing of the value of unit cost . You have:
In turn consider the ordered packages, put the considering package into knapsack if the remaining capacity of the knapsack is enough to contain it (which means that the total weight of the packages that have been put into the knapsack and weight of considering packages do not exceed the capacity of the knapsack).
Idea: The greedy idea of that problem is to calculate the ratio of each . Then sort these ratios with descending order. You will choose the highest package and the capacity of the knapsack can contain that package (remain > wi). Every time a package is put into the knapsack, it will also reduce the capacity of the knapsack. Way to select the packages:
Consider the array of unit costs. You select packages according to decreasing unit costs.
Suppose you found a partial solution: (x1, …, xi). The value of the knapsack is obtained:
Corresponding to the weight of packages that have been put into the knapsack:
Therefore, the remaining weight limit of the knapsack is:
Steps of Algorithm
You see this is a problem of finding max. The list of packages is sorted in descending order of unit costs to consider branching.
Step 1: Node root represents the initial state of the knapsack, where you have not selected any package. TotalValue = 0. The upper bound of the root node UpperBound = M * Maximum unit cost. Step 2: Node root will have child nodes corresponding to the ability to select the package with the largest unit cost. For each node, you re-calculate the parameters: TotalValue = TotalValue (old) + number of selected packages * value of each package. M = M (old) – number of packages selected * weight of each package. UpperBound = TotalValue + M (new) * The unit cost of the packaced to be considered next. Step 3: In child nodes, you will prioritize branching for the node having the larger upper bound. The children of this node correspond to the ability of selecting the next package having large unit cost. For each node, you must re-calculate the parameters TotalValue, M, UpperBound according to the formula mentioned in step 2. Step 4: Repeat Step 3 with the note: for nodes with upper bound is lower or equal values to the temporary maximum cost of an option found, you do not need to branch for that node anymore. Step 5: If all nodes are branched or cut off, the most expensive option is the one to look for.
Pseudo code for the algorithm:
Fractional Knapsack (Array W, Array V, int M)
- for i <- 1 to size (V)
- calculate cost[i] <- V[i] / W[i]
- Sort-Descending (cost)
- i ← 1
- while (i <= size(V))
- if W[i] <= M
M ← M – W[i]total ← total + V[i];- if W[i] > M
i ← i+1
The complexity of the algorithm:
If using a simple sort algorithm (selection, bubble…) then the complexity of the whole problem is O(n2). If using quick sort or merge sort then the complexity of the whole problem is O(nlogn).
Java code for Greedy Three
Firstly, you define class KnapsackPackage. This class has properties are: weight, value and corresponding cost of each package. The property cost of this class is used for sorting task in the main algorithm. The value of each cost is the ratio of each package.
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
You then create a function to perform the algorithm Greedy Three.
public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i ++) { packs[i] = new KnapsackPackage(W[i], V[i]); }
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Explanation of code:
Initialize weight and value for each knapsack package. Sort knapsack packages by cost with descending order. If select package i. If select the number of package i is enough. Stop when browsing all packages.
In this tutorial, you have two examples. Here is java code to run the above program with two examples:
public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{15, 10, 2, 4}; int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6}; int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37; int M = 15; int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
You have the output:
First Example:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
Second Example:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Analyze the first example:
The parameters of the problem are: n = 4; M = 37. The packages: {i = 1; W[i] = 15; V[i] = 30; Cost = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Cost = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Cost = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Cost = 1.5}. You sort packages in the order of no increasing of the value of unit costs. You have: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Steps for applying algorithm for the first example:
Define x1, x2, x3, x4 is the number of each selected package, corresponding to package {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}. Node root N represents the state that you have not selected any package. Then:
TotalValue = 0. M = 37 (as proposed). UpperBound = 37 * 2.5 = 92.5, of which 37 is M and 2.5 is the unit cost of package {i = 2}.
With package {i = 2}, you have 4 possibilities: select 3 package {i = 2} (x1 = 3); select 2 package {i = 2} (x1 = 2); select 1 package {i = 2} (x1 = 1) and not select package {i = 2} (x1 = 0). In accordance with these 4 possibilities, you branch the root node N to 4 children N[1], N[2], N[3] and N[4]. For child node N1, you have:
TotalValue = 0 + 3 * 25 = 75, where 3 is the number of package {i = 2} selected and 25 is the value of each package {i = 2}. M = 37 – 3 * 10 = 7, where 37 is the initial quantity of the knapsack, 3 is the number of package {i = 2}, 10 is the weight of each package {i = 2}. UpperBound = 75 + 7 * 2 = 89, where 75 is TotalValue, 7 is the remaining weight of the knapsack and 2 is the unit cost of the package {i = 1}.
Similarly, you can calculate the parameters for nodes N[2], N[3] and N[4], in which the UpperBound is 84, 79 and 74 respectively. Among nodes N[1], N[2], N[3] and N[4], node N[1] has the largest UpperBound, so you will branch node N[1] first in the hope that there will be a good plan from this direction. From node N[1], you have only one child node N[1-1] corresponding to x2 = 0 (due to the remaining weight of the backpack is 7, while the weight of each package {i = 1} is 15). After determining the parameters for the N[1-1] button you have the UpperBound of N[1-1] is 85.5. You continue branching node N[1-1]. Node N[1-1] has 2 children N[1-1-1] and N[1-1-2] corresponding to x3 = 1 and x3 = 0. After determining the parameters for these two nodes, you see that the UpperBoundary of N[1-1-1] is 84 and that of N[1-1-2] is 82, so you continue branching node N[1-1-1]. Node N[1-1-1] has two children, N[1-1-1-1] and N[1-1-1-2], corresponding to x4 = 1 and x4 = 0. These are two leaf nodes (representing the option) because for each node the number of packages has been selected. In which node N[1-1-1-1] represents the option x1 = 3, x2 = 0, x3 = 1 and x4 = 1 for 83, while node N[1-1-1-2] represents the option x1 = 3, x2 = 0, x3 = 1 and x4 = 01 at 81. So the temporary maximum value here is 83. Turning back to node N[1-1-2], you see that the UpperBound of N[1-1-2] is 82 < 83, so you trim node N[1-1-2]. Turning back to node N2, you see that the UpperBound of N2 is 84 > 83, so you continue branching node N2. The node N2 has two children N[2-1] and N[2-2] corresponding to x2 = 1 and x2 = 0. After calculating the parameters for N[2-1] and N[2-2], you see the UpperBound of N[2-1] is 83 and that of N[2-2] is 75.25. Neither of these values is greater than 83 so both nodes are trimmed. Finally, nodes N3 and N4 are also trimmed. So all the nodes on the tree are branched or trimmed so the best temporary solution is the one to look for. Accordingly, you need to select 3 packages {i = 2}, 1 package {i = 4} and one package {i = 3} with total value of 83, total weight is 36.
With the same analysis of the second example, you have the result: select package 4 (3 times) and package 5 (3 times).
Python3 code for Greedy Three
Firstly, you define class KnapsackPackage.
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
You then create a function to perform the algorithm Greedy Three.
class FractionalKnapsack(object): def init(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Explanation of code:
Initialize weight and value for each knapsack package. Sort knapsack packages by cost with descending order. If select package i. If select the number of package i is enough. Stop when browsing all packages.
Here is Python3 code to run the above program with the first example:
if name == “main”: W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
You have the output:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
C# code for Greedy Three
Firstly, you define class KnapsackPackage.
using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
You then create a function to perform the algorithm Greedy Three.
using System; namespace KnapsackProblem { public class FractionalKnapsack { public FractionalKnapsack() { }
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Explanation of code:
Initialize weight and value for each knapsack package. Sort knapsack packages by cost with descending order. If select package i. If select the number of package i is enough. Stop when browsing all packages.
Here is C# code to run the above program with the first example:
public void run() { /* * Pack and Weight - Value */ int[] W = new int[]{15, 10, 2, 4}; //int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
You have the output:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Counter-example of Greedy Three
The algorithm of Greedy Three resolves quickly and can also be optimal in some cases. However, in some special cases, it does not give the optimal solution. Here you have a counter-example:
The parameters of the problem are: n = 3; M = 10. The packages: {i = 1; W[i] = 7; V[i] = 9; Cost = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Cost = 1}; {i = 3; W[i] = 4; V[i] = 4; Cost = 1}. The algorithm will select (package 1) with a total value of 9, while the optimal solution of the problem is (package 2, package 3) with a total value of 10.
Here is java code to run the above program with the counter-example:
public void run() { /* * Pack and Weight - Value */ int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Here is the result:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
That’s all to Fractional Knapsack problem.
