Package topics.greedy

package topics.greedy

Greedy algorithms — globally optimal solutions through locally optimal choices.

A greedy algorithm always selects the locally best option at each step without reconsidering previous decisions. When the problem satisfies the greedy-choice property and optimal substructure, the greedy strategy yields a globally optimal solution — usually in O(n log n) or better.

When Greedy Works

• Greedy-choice property — a locally optimal choice is always part of some globally optimal solution.
• Optimal substructure — the optimal solution to the whole problem contains optimal solutions to its sub-problems.

When Greedy Fails

Consider coin change with denominations {1, 3, 4} and target 6:

• Greedy picks 4 + 1 + 1 = 3 coins
• Optimal is 3 + 3 = 2 coins

In such cases, Dynamic Programming or Branch & Bound is required.

Classes in This Package

• AgentsTasks — greedy assignment of agents to tasks
• Change — greedy coin-change (may not be optimal)
• ChessHorse — greedy knight's-tour heuristic
• ChessHorseSimpleHeuristic — simpler knight's-tour heuristic
• FilesDisc1 — greedy file-packing on a disc (variant 1)
• FilesDisc2 — greedy file-packing on a disc (variant 2)
• Knapsack — fractional knapsack (greedy is optimal)
• Knapsack01 — 0/1 knapsack (greedy is not optimal)
• Plumber — greedy plumber scheduling
• SomePlumbers — multi-plumber scheduling variant

Related Packages

Package	Description
topics.greedy.agentsTasks	Execution-time benchmarks for greedy agents-to-tasks assignment.

Classes

Class	Description
AgentsTasks	GREEDY ALGORITHM PROBLEM: THE PROBLEM OF ASSIGNING N TASK TO AGENTS This program can solve the problem using two greedy algorithms and test operation.
Change	GREEDY ALGORITHM PROBLEM: THE PROBLEM OF THE CHANGE OF MONEY It has an optimal solution in some cases.
ChessHorse	GREEDY ALGORITHM PROBLEM: THE HORSE JUMPING PROBLEM (Knight's tour) It has not an optimal solution in some cases
ChessHorseSimpleHeuristic	GREEDY ALGORITHM PROBLEM: THE HORSE JUMPING PROBLEM (Knight's tour) It has not an optimal solution in some cases
FilesDisc1	GREEDY ALGORITHM PROBLEM: MAXIMIZE THE NUMBER OF FILES ON A DISK It has an optimal solution.
FilesDisc2	GREEDY ALGORITHM PROBLEM: MINIMIZE THE FREE SPACE ON A DISK WITH FILES It has NOT an optimal solution in some cases.
Knapsack	GREEDY ALGORITHM PROBLEM: THE KNAPSACK PROBLEM (BREAKABLE) it has an optimal solution
Knapsack01	GREEDY ALGORITHM PROBLEM: THE KNAPSACK PROBLEM (0/1).
Plumber	Single-plumber scheduling utility.
SomePlumbers	GREEDY ALGORITHM PROBLEM: SOME DILIGENT PLUMBERS It has an optimal solution