Hello again.

**WARNING**[/list]

ToohTooh cannot warrant that this code will always generate optimal solution sets, or even generate a correct solution. Although algorithm is based on a scientific approach, ToohTooh's implementation may include some incorrections.

**NOTICE**[/list]

Before working to find out how it works, make sure that you understand the data structure it uses well!..

First off, as a die-hard QBer, I'd like to state that contributing to challenges more often as time permits is so warm (what's warm, anyway?). Thanks again, na_th_an!..

This below is the Optimal Approach using the divide-and-conquer strategy.

It's very fast, simple, short, effective and much like those you can find in text books (just because it's being tuned for days).

To take advantage of repetitive works of its recursive-approach predecessor which I haven't released, it allocates some memory and begins building Amount from ground up generating results very fast.

**NOTICE:** I dropped FindLimit(), and Sort(). They create too much mess, and are pretty off-topic. If you want them anyway, you may copy them from my code in a past post titled

' ***

'-- na_th_an's Coin Challenge: The Greedy Approach

'-- Explore under QB IDE.

' ***

and paste to this one.

**HISTORY:** This new Change() derived from recursive-version's Change() and FindNumber(Amount) functions. Old Change() had nothing to do but to map results of FindNumber(Amount) to So(). FindNumber(Amount) would recursively find every possible So()'s for every Va(). Now, it integrated into this new Change(), leaving only the idea behind.

Initial non-recursive version had the following

FOR i = 1 TO Amount

FOR ii = 1 TO Limit

IF i >= ii THEN

div = i \ ii

IF div >= minDiv THEN

minDiv = div

loMaker = ii

END IF

END IF

NEXT ii

nrCoins(i) = minDiv

amtToVa(i) = loMaker

NEXT i

instead of the one posted below. You can see that, the

div = i \ ii

IF div >= minDiv THEN

...

END IF

structure is a heritage from my very early greedy approach version.

Presence of this structure created some problems: It, by default, assumed a greedy approach and tried to construct every amount with minimum number of available Va() and it failed as it tended to grab greater Va()s.

It also lacked an assumption: If no divs can be computed at a pass, we had to feed the algorithm with a default (namely, the first) Va():

minDiv = 1

loMaker = 1

Second rewrite brought the skeleton of the algorithm posted below with a difference such that a forced-first-assign like

IF bldThis < 0 THEN bldThis = 0

min = nrCoins(bldThis)

prospVaInd = 1

END IF

appeared instead of the sanity check

IF (bldThis >= 0) THEN

...

END IF

of the one below. This can be explained as follows: If an Amount is unconstructable with present Va() set (this happens at the early pass stages where FOR..NEXT produces very low i amount values), then a prospective Va() index assumption shouldn't be made as including present Va()s will just corrupt the result.

**TECHNICAL:** Consider partitions of Amount whose summands are taken (repetitions allowed) from a sequence of integers

Va() : (Va1, Va2, ...); 1 <= Va1 < Va2 < ... [1]

Giving such a partition [1] is equivalent to giving a solution of

(n1 x Va1) + (n2 x Va2) + (n3 x Va3) + ... = Amount; n_i, Va_i nonnegative integers. [2]

Generating solutions to [2] with respect to sequence [1] is defined as

Change(Amount; Va()) = Change(Amount; Va1, Va2, ...) [3]

Code I posted aims to generate a solution to the described problem with assumption such that

n1 + n2 + ... = n_total -> min [4]

Algorithm for [3] create a solution set for [2] strictly adhering to [4], guaranteeing [2] with a correction such that

(n1 x Va1) + (n2 x Va2) + (n3 x Va3) + ... = Amount + e; n_i, Va_i, nonnegative integers; e, positive integer or 0. [5]

where e stands for the output error (namely, the mismatched Amount).

For a [4] yielding a

in [5] requires you to strictly include Va(1) = 1 to the coin (denumerant) set (as already described in [1]). This way, you can always guarantee a solution, although not necessarily the optimal one.

This code also demonstrates the trade-offs between in "gain-in-time, lose-in-space" rule (use memory, forget recursion).

Feel free to test and tangle.

' ***

'-- na_th_an's Coin Challenge: The Optimal Approach

'-- Explore under QB IDE.

' ***

'-- This is an Intermediate / Advance level implementation of the challenge

' which demonstrates the uses of divide-and-conquer approach of

' Computer Science.

'-- Rewritten several times so non-recursive.

'-- All of its magic lies behind the memory use and taking advantage of

' repetitive works. Print this out and work it 'on paper,' too.

'-- ToohTooh cannot warrant that this code will always generate optimal

' solution sets, or even generate a correct solution.

'-- ToohTooh, in Istanbul City.

DEFINT A-Z

DECLARE FUNCTION Change (Va(), Limit, Amount, So())

TYPE buildTAG '>> Further info in Change()

amtToVa AS INTEGER

nrCoins AS INTEGER

END TYPE

'-- At every change, make sure you re-assign myLimit and sort values().

myLimit = 3: DIM values(myLimit), solution(myLimit)

values(0) = 1

values(1) = 3

values(2) = 5

values(3) = 7

myAmount = 9

CLS

PRINT "Worked for"; RTRIM$(STR$(myAmount));

result = Change(values(), myLimit, myAmount, solution())

PRINT ".": PRINT "Let's see... We have"

FOR i = 0 TO UBOUND(solution)

IF solution(i) <> 0 THEN PRINT solution(i); "coin(s) valued at"; values(i)

NEXT i

'-- myAmount of below may have a sign, so LTRIM it also.

PRINT "to remain a total of "; LTRIM$(RTRIM$(STR$(myAmount))); "."

IF NOT result THEN PRINT "Criteria couldn't be met with present values()."

END '>> Main

FUNCTION Change (Va(), Limit, Amount, So()) '>> So() assumed to have been

' pre-initialized to zeroes.

DIM bld(1024) AS buildTAG '>> Will store results of repetitive calc.s

'-- Say, Va(k) and So(k). This tells us that 'So(k) number of coins valued at

' Va(k) are reserved for optimal solution.'

'-- Say (bld.nrCoins(x) = m) and (bld.amtToVa(x) = t). This tells that

' 'm number of coins valued at Va(t) are required to construct Amount x.'

FOR i = 1 TO Amount

bldThis = i - Va(1)

IF (bldThis >= 0) THEN '>> Sanity check.

'-- Special case for Va(1). Va(1) is considered to be the lowest coin

min = bld(bldThis).nrCoins ' capable of building every Amount

prospVaInd = 1 ' (not necessarily the optimal one).

END IF

FOR ii = 2 TO Limit '>> 1 was special case so start from 2.

'-- Every other Va(ii), check for minimums.

bldThis = i - Va(ii)

IF (bldThis >= 0) THEN '>> i.e.: Using Va(ii) logical (positive)?

IF (bld(bldThis).nrCoins < min) THEN

'-- A new minimum and so, a new prospective Va() index.

min = bld(bldThis).nrCoins

prospVaInd = ii

END IF

END IF

NEXT ii

'-- If no new prospVaInds, old ones still go okay

' (for the fact that new i's (amounts): i(n) < i(n + 1) ).

bld(i).amtToVa = prospVaInd

'-- Every other i, increment nr. of coins (w/o caring constructed

' total will exceed Amount: This way, So() this FUNC returns

' always construct worst case amounts greater than input Amount.)

bld(i).nrCoins = min + 1

NEXT i

Change = -1 '>> Change() default.

WHILE (Amount > 0)

index = bld(Amount).amtToVa

So(index) = So(index) + 1 '>> Build So() decrementing Amount.

Amount = Amount - Va(index)

WEND

IF Amount <> 0 THEN Change = 0 '>> Return err for positive(?)/negative Amount.

END FUNCTION '>> Change()