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