Greedy Algorithms

Sample programs showing solutions to puzzles solved using Greedy Algorithm.

Problem 1 Money Change

Compute the minimum number of coins needed to change the given value into coins with denominations 1, 5, and 10. Input. An integer money. Output. The minimum number of coins with denominations 1, 5, and 10 that changes money.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 216). Active Learning Technologies. Kindle Edition.

Problem 2 Maximizing the Value of the Loot

Find the maximal value of items that fit into the backpack. Input. The capacity of a backpack W as well as the weights (w1 ,...,wn) and per pound prices (p1 ,..., pn) of n different compounds. Output. The maximum total price of items that fit into the backpack of the given capacity: i.e., the maximum value of p1 · u1 + ··· + pn · un such that u1+···+un ≤ W and 0 ≤ ui ≤ wi for all i.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 217). Active Learning Technologies. Kindle Edition.

Problem 3 Car Fueling

Compute the minimum number of gas tank refills to get from one city to another. Input. Integers d and m as well as a sequence of integers stop1 < stop2 < ··· < stopn. Output. The minimum number of refills to get from one city to another in a car can travel at most m miles on a full tank. The distance between the cities is d miles and there are gas stations at distances stop1, stop2 ,..., stopn along the way.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 218). Active Learning Technologies. Kindle Edition.

Problem 4 Maximum Product of Two Sequences

Find the maximum dot product of two sequences of numbers. Input. Two sequences of n positive integers: price1 ,...,pricen and clicks1 ,...,clicksn. Output. The maximum value of price1 · c1 + ··· + pricen · cn, where c1 ,..., cn is a permutation of clicks1 ,...,clicksn.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 219). Active Learning Technologies. Kindle Edition.

Problem 5 Covering Segments by Points

Find the minimum number of points needed to cover all given segments on a line. Input. A sequence of n segments [l1, r1 ],...,[ln, rn] on a line. Output. A set of points of minimum size such that each segment [li, ri] contains a point, i.e., there exists a point x such that li ≤ x ≤ ri.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 220). Active Learning Technologies. Kindle Edition.

Problem 6 Distinct Summands

Represent a positive integer as the sum of the maximum number of pairwise distinct positive integers. Input. An integer n. Output. The maximum k such that n can be represented as the sum a1+···+ak of k distinct integers. Resume Largest Concatenate Compile the largest number by concatenating the given numbers. Input. A sequence of positive integers. Output. The largest number that can be obtained by concatenating the given integers in some order.

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 221). Active Learning Technologies. Kindle Edition.

Problem 7 Largest Concatenate

Compile the largest number by concatenating the given numbers. Input. A sequence of positive integers. Output. The largest number that can be obtained by concatenating the given integers in some order. 221

Kulikov, Alexander S.; Pevzner, Pavel. Learning Algorithms Through Programming and Puzzle Solving (p. 221). Active Learning Technologies. Kindle Edition.