Comment on page
Greedy Algorithm
- Greedy algorithms are applied to optimization algorithms only.
- It picks always the current best solution; no backtracking.
- Not necessarily optimal --> need to prove it.
- find a set of items that can
- meet some constraints, and
- optimize some objective function
- examples: shortest path, minimum spanning tree
- not an optimization problem: sorting
To prove the optimality of a greedy strategy, we need to prove the following two parts.
- Greedy Choice
- find the choice that is part of SOME optimal solution
- there may exist multiple optimal solutions; no need to prove it for ANY optimal solution
- Optimal Substructure
- After making the first choice, the final best solution is first choice + best solution for the rest of (compatible) input
- We can solve the same optimization problem recursively!
- Otherwise, we find a contradiction!
- activity selection (pick the earliest-finish task)
- minimum spanning tree
- Huffman code
- Dijkastra's shortest path
- graph coloring
- traveling salesman
- Greedy: always pick the current best
- DP: pick the best based on history
- You can always use DP to solve Activity Selection problem, but it is much costly (since you have to try all other branches)
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
int n;
std::cin >> n;
std::vector<int> candies(n);
for (int k = 0; k < n; ++k)
std::cin >> candies[k];
// count total number of 1s, 2s, 3s
int sum1 = 0, sum2 = 0, sum3 = 0;
for (int k = 0; k < n; ++k){
if (candies[k] == 1)
sum1++;
else if (candies[k] == 2)
sum2++;
else
sum3++;
}
// all 3s should be placed in the range [sum1+sum2, n-1]
// and then leave a subproblem of 1s and 2s in the range [0, sum1+sum2-1]
int swap = 0;
std::vector<int> temp_queue;
for (int k = sum1 + sum2; k < n; ++k){
if (candies[k] != 3){
swap++;
temp_queue.push_back(candies[k]);
}
}
// move all 1s to the front and 2s to the end
std::sort(temp_queue.begin(), temp_queue.end());
// in [0, sum1+sum2-1], we want to put 1s to the front and 2s to the end
for (int k = sum1 + sum2 - 1; k >= 0; --k){
if (candies[k] == 3){
candies[k] = temp_queue.back();
temp_queue.pop_back();
}
}
// finally, count how many 2s are still there in the range [0, sum1-1]
// which is supposed to be all 1s
for (int k = 0; k < sum1; ++k){
if (candies[k] == 2)
swap++;
}
std::cout << swap << std::endl;
return 0;
}
Last modified 2yr ago