Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [greedy-algorithms]

Questions about algorithms that make at each step the locally optimal choice.

25
votes
2answers
22k views

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...
5
votes
2answers
5k views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
19
votes
4answers
1k views

How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-...
2
votes
1answer
82 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
4
votes
1answer
454 views

Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
-1
votes
1answer
1k views

Minimal Spanning tree and Prim's Algorithm

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.
23
votes
1answer
25k views

When can a greedy algorithm solve the coin change problem?

Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v. E.g. for the coinset 1,5,10,20 this gives 2 ...
13
votes
2answers
10k views

Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal. For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover). For each ...
2
votes
1answer
476 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
4
votes
1answer
402 views

Greedy algorithm correctness proof for “Elegant Permuted Sum” (UVa 11158)

Given a sequence of $2 \leq n \leq 50$ numbers $s = (s_1,s_2,...,s_n)$, find a permutation $a = (a_1,a_2,...,a_n)$ of $s$ such that $$\sum_{i=1}^{n-1} |a_i - a_{i+1}|$$ is maximized. I found many ...
4
votes
1answer
902 views

Greedy algorithms: Minimum sum number pairing

Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair. I think the optimal pairing is obtained by sorting the original set, pairing the first element ...
3
votes
4answers
2k views

Confusion in CLRS's version of Prim's algorithm

The algorithm is as follows: ...
3
votes
1answer
144 views

Greedy algorithm proof

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}. When we buy the products in pairs we get the product with lower ...
2
votes
1answer
96 views

Selecting optimal order of questions to minimize total time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
2
votes
1answer
137 views

Proof for This Greedy Strategy for Equalizing An Array

Recently the following problem was posed in a private coding competition at my workplace: An array $A$ is given that has only positive integers in it. The objective is to equalize the array in ...
1
vote
1answer
323 views

Proof of a greedy algorithm concerning “Buy and Resell Problem”

"Buy and Resell Problem" can be described in the following way: There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from ...
3
votes
2answers
721 views

set with maximum sum consisting of mutually co-prime numbers

Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have. Example. Let $n=10$, ...
2
votes
1answer
2k views

Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some ...
2
votes
4answers
254 views

A greedy algorithm for the bottle filling problem

(There’s no need to write the algorithm, I just need help with the greedy choice). Problem: you are given bottles numbered 1 to n. Each bottle i has a capacity of Ci and currently contains Li. We ...
1
vote
1answer
810 views

How to prove greedy algorithm for number partitioning?

the partition problem (or number partitioning1) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the ...
1
vote
2answers
56 views

Minimum spanning tree such that one edge can be minimised

During a computer coding exam, I have encountered such a problem. Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the ...