Greedy Approach and Puzzles

• Change making with single coins -Bachet(1612)-Fibonacci(1202) weighing problemFind an optimal set of n weights:

{q1, q2, ..., qn}

So that it is possible to weigh any integral load in the range from 1 up to Q and so that Q is maximized.

(no repetitions of weights allowed)

• Use only the free cup of the balance: qi = 2i-1, i=1,2,...

• Both cups of the balance allowed: qi = 3i-1, i=1,2,...

Previous slide

Next slide

Back to first slide

View graphic version