Totally greedy coin sets and greedy obstructions (Q1010817): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 02:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Totally greedy coin sets and greedy obstructions |
scientific article |
Statements
Totally greedy coin sets and greedy obstructions (English)
0 references
7 April 2009
0 references
Summary: A coin set is a strictly increasing list of positive integers that always begins with 1. A coin set is called greedy when the simple greedy change-making algorithm always produces the fewest number of coins in change. Here, the greedy change-making algorithm repeatedly selects the largest denomination coin less than the remaining amount until it has assembled the correct change. Pearson has provided an efficient algorithm for determining whether a coin set is greedy. We study a stricter property on coin sets, called total greediness, which requires that all initial subsequences of the coin set also be greedy, and a simple property makes it easy to test if a coin set is totally greedy. We begin to explore the theory of greedy obstructions --- those coin sets that cannot be extended to greedy coin sets by the addition of coins in larger denominations.
0 references
coin set
0 references
greedy coin set
0 references
change making algorithm
0 references
total greediness
0 references
initial subsequences
0 references
greedy obstructions
0 references
denominations
0 references