Greedy algorithm is a very common algorithm idea, and it is easy to understand because it conforms to the general habits of people’s thinking. Let’s talk about greedy algorithms from the beginning.
Change the problem
Let’s start with an easier question:
Suppose you are a shop owner and you need to give a customer change of N yuan. You have money in denominations of 100 yuan, 50 yuan, 20 yuan, 5 yuan, 1 yuan. How can I get the least amount of change I need?
Example: If you need 126 yuan change, the least amount of coins you need is 100 yuan per change, 20 yuan per bill, 5 yuan per bill, and 1 yuan per bill.
This question is very common in our life, we often encounter when shopping, so how do we generally think? Suppose that we need to change 126 dollars, we can look at to find how much is the largest denomination, we found that a 126-100, it can certainly find a 100 piece, and then the remaining 26 yuan, look at what is the largest denomination 26 can match, found is 20, that find a 20, and then there were six blocks, the same train of thought, looking for a 5 piece and 1 piece. That’s the idea of greedy algorithms, greedy every time to find the biggest match, and then find the next big one. The algorithm code is also easy to write:
const allMoney = [100.50.20.5.1]; // indicates the denominations we have
function changeMoney(n, allMoney) {
const length = allMoney.length;
const result = []; // An array of results, each representing the number of pieces corresponding to the value
for(let i = 0; i < length; i++) {
if(n >= allMoney[i]) {
// If the change is larger than the face value, divide and see how many you can find
result[i] = parseInt(n / allMoney[i]);
n = n - result[i] * allMoney[i]; // Update the remaining change
} else {
// Otherwise you can't find it
result[i] = 0; }}return result;
}
const result = changeMoney(126, allMoney);
console.log(result); // [1, 0, 1, 1, 1]
Copy the codeGreedy algorithm
The above change problem is greedy algorithm, every time to corrupt the largest face value, found not corrupt, and then corrupt times big. Conceptually, greedy algorithms are:
As can be seen from the above definition, not all problems can be solved by greedy algorithm, because it only gets local optimal solutions each time, and the combination of local optimal solutions is not necessarily the global optimal solution. Here’s an example:
Knapsack problem
Backpack problem is also a very classic algorithm problem, the title is as follows:
There was a thief who went into a shop to steal something. There were a lot of things in the shop, each of which had a value of V and a weight of W. But the thief only had one backpack, and the total weight of his backpack was W. Can you tell me how to get the most value out of something?
In fact, the backpack problem can be subdivided into two problems: 0-1 backpack and score backpack.
0-1 backpack: Refers to an item that you either don’t take or you take it all, not half or two-thirds. You can think of commodities as bullion, you either take the whole piece or you don’t take half of it.
Score backpack: A score backpack is the opposite of a 0-1 backpack. You can take only part of it, half of it, or two-thirds of it. You can think of the commodity as gold sand, you can just take a part of it.
Here’s an example:
This problem is also very good in our thinking. If we want to get the maximum total value, we just take the most expensive one, that is, the number of value divided by weight is the largest. But if you take the most expensive item every time, will the total value be the highest? Let’s assume that the example above is 0-1 backpack, the most expensive is V1, then V2, then V3. So let’s take v1, we have 40 left, we get 60, and then v2, we have 20 left, we get 160. And then I couldn’t carry it, because the V3 weighed 30, and we only had 20 left in the backpack. But this is obviously not the global optimal solution, because it’s obvious that if we take v2, v3, and the backpack is just full, the total value is 220, that’s the optimal solution. So the 0-1 knapsack problem can’t be greedy.
But score packs can be used with greed, because we can always take the most expensive. We took v1, we took v2, and we found that v3 didn’t fit, so we’re done. We’ll just fill it two-thirds. Here we use greed to implement a score backpack:
const products = [
{id:1.v: 60.w: 10},
{id:2.v: 100.w: 20},
{id:3.v: 120.w: 30}];// Create an array to represent a list of items, with each item identified by an ID
function backpack(W, products) {
const sortedProducts = products.sort((product1, product2) = > {
const price1 = product1.v / product1.w;
const price2 = product2.v / product2.w;
if(price1 > price2) {
return -1;
} else if(price1 < price2) {
return 1;
}
return 0;
}); // Start by sorting the items in order of value
const result = []; // Create a new array to receive the result
let allValue = 0; // The total value obtained
const length = sortedProducts.length;
for(let i = 0; i < length; i++) {
const sortedProduct = sortedProducts[i];
if(W >= sortedProduct.w) {
// Take the whole thing
result.push({
id: sortedProduct.id,
take: 1.// The quantity to take
});
W = W - sortedProduct.w;
allValue = allValue + sortedProduct.v;
} else if(W > 0) {
// Only part of it
result.push({
id: sortedProduct.id,
take: W / sortedProduct.w,
});
allValue = allValue + sortedProduct.v * (W / sortedProduct.w);
W = 0; / / is full of
} else {
// I can't take it
result.push({
id: sortedProduct.id,
take: 0}); }}return {result: result, allValue: allValue};
}
// Test it
const result = backpack(50, products);
console.log(result);
Copy the codeRunning results:
0-1 knapsack
We’ve already said that 0-1 knapsack can’t be solved by greed, so let’s talk about how it can be solved. To solve this problem you need to use the idea of dynamic programming, and for the idea of dynamic programming, you can read my article, but if you just want to look at greedy algorithms, you can skip this part. Let’s say we have n items in our backpack, and W is the total capacity of our backpack, and the total value we have is D(n,W)D(n, W)D(n,W). Let’s think about the last step,
If we omit the last item, the total value is D(n−1,W)D(n-1, W)D(n−1,W)
If the last good is added, the total value is vn+D(n−1,W− WN) v_N +D(N-1, W-W_N) vN +D(N −1,W− WN). The following conditions are met: W>= WN W>= w_nW>= WN. The last one has to fit.
The maximum solution we require is actually the maximum value of the above two schemes, expressed as follows:
The recursive method
With the recursive formula, we can use the recursive solution:
const products = [
{id:1.v: 60.w: 10},
{id:2.v: 100.w: 20},
{id:3.v: 120.w: 30}];// Create an array to represent a list of items, with each item identified by an ID
function backpack01(n, W, products) {
if(n < 0 || W <= 0) {
return 0;
}
const noLast = backpack01(n-1, W, products); // Do not put the last one
let getLast = 0;
if(W >= products[n].w){ // If the last one fits
getLast = products[n].v + backpack01(n-1, W-products[n].w, products);
}
const result = Math.max(noLast, getLast);
return result;
}
// Test it
const result = backpack01(products.length-1.50, products);
console.log(result); / / 220
Copy the codeDynamic programming
The recursion is very complex, so let’s rewrite it using dynamic programming:
const products = [
{id:1.v: 60.w: 10},
{id:2.v: 100.w: 20},
{id:3.v: 120.w: 30}];// Create an array to represent a list of items, with each item identified by an ID
function backpack01(W, products) {
const d = []; // Initialize an array to calculate the intermediate value
const length = products.length;
// I represents the number of items, the number is 0 -- (length-1)
// j stands for column, is the knapsack capacity, the number is 0 -- W
for(let i = 0; i < length; i++){
d.push([]);
for(let j = 0; j <= W; j++) {
if(j === 0) {
// The backpack capacity is 0
d[i][j] = 0;
} else if(i === 0) {
if(j >= products[i].w) {
// Can drop the first item
d[i][j] = products[i].v;
} else {
d[i][j] = 0; }}else {
const noLast = d[i-1][j];
let getLast = 0;
if(j >= products[i].w) {
getLast = products[i].v + d[i-1][j - products[i].w];
}
if(noLast > getLast) {
d[i][j] = noLast;
} else{ d[i][j] = getLast; }}}}console.log(d);
return d[length-1][W];
}
// Test it
const result = backpack01(50, products);
console.log(result); / / 220
Copy the codeBackward optimal solution
To be able to output the optimal solution, we need to record every last item we put in, and then work backwards from the end, reworking the previous code as follows:
const products = [
{id:1.v: 60.w: 10},
{id:2.v: 100.w: 20},
{id:3.v: 120.w: 30}];// Create an array to represent a list of items, with each item identified by an ID
function backpack01(W, products) {
const d = []; // Initialize an array to calculate the intermediate value
const res = []; // Record the last item placed each time, also a two-dimensional array
const length = products.length;
// I represents the number of items, the number is 0 -- (length-1)
// j stands for column, is the knapsack capacity, the number is 0 -- W
for(let i = 0; i < length; i++){
d.push([]);
res.push([]);
for(let j = 0; j <= W; j++) {
if(j === 0) {
// The backpack capacity is 0
d[i][j] = 0;
res[i][j] = null;
} else if(i === 0) {
if(j >= products[i].w) {
// Can drop the first item
d[i][j] = products[i].v;
res[i][j] = products[i];
} else {
d[i][j] = 0;
res[i][j] = null; }}else {
const noLast = d[i-1][j];
let getLast = 0;
if(j >= products[i].w) {
getLast = products[i].v + d[i-1][j - products[i].w];
}
if(noLast > getLast) {
d[i][j] = noLast;
} else {
d[i][j] = getLast;
res[i][j] = products[i]; // Record the last item}}}}// Backtrace the res to get the optimal solution
let tempW = W;
let tempI = length - 1;
const bestSol = [];
while (tempW > 0 && tempI >= 0) {
const last = res[tempI][tempW];
bestSol.push(last);
tempW = tempW - last.w;
tempI = tempI - 1;
}
console.log(d);
console.log(bestSol);
return {
totalValue: d[length-1][W],
solution: bestSol
}
}
// Test it
const result = backpack01(50, products);
console.log(result); / / 220
Copy the codeOutput from the code above:
Digital Mosaic problem
Let’s look at another greedy algorithm problem, just to make sense of it, which is as follows:
This problem also seems easy, we sometimes encounter similar problems, we can intuitively think of a solution: to see which number the first digit is large, put them in front, such as 32 and 94, put 94 in front of the first digit is 9, get 9432, is definitely larger than 32 put in front of 3294. Sort by string size, first by character, but is this correct? Let’s look at two more numbers, if we have 728 and 7286, and we put 7286 first in character order, we get 7286728, but it’s not as big as 7287286. If two numbers, a and B, are the same length, then it works. If they’re not the same length, then it doesn’t work. So what do we do? Well, it’s easy. Let’s look at the numbers a+b and b+a make up, and whichever is bigger.
Let's say that a = 728 and b = 7286 string A + B = "7287286" string B + a = "7286728"Copy the codeThe above algorithm is a greedy, what is greedy here? It’s a plus b, the bigger one. We can either write a bubble or use the array sort method:
const nums = [32.94.128.1286.6.71];
function getBigNum(nums) {
nums.sort((a, b) = > {
const ab = `${a}${b}`;
const ba = `${b}${a}`;
if(ab > ba) {
return -1; // When ab is bigger, a comes first
} else if (ab < ba) {
return 1;
}
return 0;
});
return nums;
}
const res = getBigNum(nums);
console.log(res); // [94, 71, 6, 32, 1286, 128]
Copy the codeActivity selection problem
Activity selection problem is a little more difficult, you can also use greed, but need to greedy things not so intuitive in front of the topic, let’s take a look at the topic:
This problem should be considered as follows: in order to arrange as many activities as possible, when we arrange one activity, we should try to leave more time for the following activities, so that we can arrange more activities later. In other words, schedule the activities with the earliest end time first, and then schedule the activities with the earliest end time for the rest of the time. In fact, the greedy here is the early end time, this conclusion can be proved by mathematics:
Let’s implement the following code:
const activities = [
{start: 1.end: 4},
{start: 3.end: 5},
{start: 0.end: 6},
{start: 5.end: 7},
{start: 3.end: 9},
{start: 5.end: 9},
{start: 6.end: 10},
{start: 8.end: 11},
{start: 8.end: 12},
{start: 2.end: 14},
{start: 12.end: 16},];function chooseActivity(activities) {
// Start by sorting the end time from smallest to largest
activities.sort((act1, act2) = > {
if(act1.end < act2.end) {
return -1;
} else if(act1.end > act2.end) {
return 1;
}
return 0;
});
const res = []; // Receive an array of results
let lastEnd = 0; // Record the end time of the last activity
for(let i = 0; i < activities.length; i++){
const act = activities[i];
if(act.start >= lastEnd) {
res.push(act);
lastEnd = act.end
}
}
return res;
}
// Test it
const result = chooseActivity(activities);
console.log(result);
Copy the codeThe code above runs as follows:
conclusion
The focus of the greedy algorithm is a greedy word, to find the object of the greedy, and then constantly greedy, finally put the target greedy, output the optimal solution. It should be noted that every time you are greedy, in fact, you only get the local optimal solution, the local optimal solution does not necessarily constitute the global optimal solution, such as 0-1 backpack, for this problem is not greedy, to use other methods to solve.
At the end of this article, thank you for your precious time to read this article. If this article gives you a little help or inspiration, please do not spare your thumbs up and GitHub stars. Your support is the motivation of the author’s continuous creation.
Welcome to follow my public numberThe big front end of the attackThe first time to obtain high quality original ~
“Front-end Advanced Knowledge” series:Juejin. Cn/post / 684490…
“Front-end advanced knowledge” series article source code GitHub address:Github.com/dennis-jian…