Introduction to Greedy Algorithms

A greedy algorithm commits to a locally preferred choice and does not reconsider it later. That can produce a global optimum, but only when the problem structure makes the commitment safe. In competitive programming the difficult part is usually the proof, not the sort or loop. We begin with a simple purchasing problem: every item has equal benefit, costs are nonnegative, and the goal is to buy as many items as possible within a budget.

Prerequisites: Fundamentals: arrays, sorting, sums and asymptotic complexity. Related existing lessons: Introduction to Sorting.

Build the idea

1. Specify the objective before choosing

   Let costs be c1…cn and budget B. We maximize the number of purchased items, not their value or the money spent. Every item is available once and gives exactly one unit of benefit. Nonnegative costs mean adding an item never creates extra budget. Changing any of these assumptions can change the algorithm: a high-value expensive item may matter in a value-maximization problem.

2. Make the greedy choice

   Sort costs in ascending order and repeatedly buy the cheapest remaining item while it fits. spent tracks the sum of the accepted prefix and count its length. If the next cost exceeds B−spent, stop; every later cost is at least as large. Comparing with remaining budget also avoids computing a potentially excessive trial sum.

   $$\Sigma \mathrm{cheapest}\left(k\right)\le \Sigma \mathrm{any}\left(k\right)$$

3. Correctness proof: the cheapest prefix stays ahead

   For any fixed k, the k smallest costs have minimum possible total among all k-item subsets. If a chosen subset contains a more expensive item while omitting a cheaper one, exchange them without increasing cost; repeated exchanges yield the sorted prefix. Thus whenever the greedy (k+1)-prefix exceeds B, every (k+1)-subset exceeds B. The accepted prefix is feasible and no larger purchase is possible.

4. Trace the sample

   With costs [4,1,2,6,3] and B=7, sorting gives [1,2,3,4,6]. Buy 1, then 2, then 3: count=3 and spent=6. The next cost 4 exceeds the remaining budget 1, so stop. Spending exactly the full budget is not required; the objective is cardinality. Zero-cost items are accepted even with an initially zero budget.

5. Know when to change methods

   The greedy-choice property means some optimum can begin with the proposed decision; optimal substructure means the remaining decisions form the corresponding smaller problem. Both need justification. Largest-coin-first fails for coins {1,3,4} and amount 6: 4+1+1 loses to 3+3. Brute force explores alternatives and dynamic programming combines states when one irrevocable choice is unsafe; they are proof tools as well as solution methods.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n;
    long long budget;
    std::cin>>n>>budget;
    std::vector<long long>cost(n);
    for(auto&x:cost){
        std::cin>>x;
    }
    std::sort(cost.begin(),cost.end());
    long long spent=0;
    int count=0;
    for(long long x:cost){
        if(x>budget-spent){
            break;
        }
        spent+=x;
        ++count;
    } // Cheapest prefix has minimum cost for its size.
    std::cout<<count<<' '<<spent<<'\n';
}

Complexity analysis

O(n log n) sorting, O(n) scan, O(n) input storage; the accepted-prefix state is O(1). spent never exceeds the budget. Sorting is useful because it exposes the minimum-cost prefix for every cardinality.

Example input and output

Read n (0..100000), budget B (0..10^12), then n item costs in 0..10^9. Print maximum item count and the cost of the chosen cheapest prefix.

Input

5 7
4 1 2 6 3

Output

3 6

The cheapest three cost 6, while the cheapest four cost 10, so no four-item subset fits.

Practical applications

Look for exchangeable equal-benefit objects and a single additive budget. Compare the proof against weighted variants before reusing the code. Activity selection uses a different greedy criterion because time conflicts are not additive item costs.

Check your understanding

Why can the program stop at the first unaffordable sorted cost?

Put it into practice

Find a small example where cheapest-first fails when items have different values.