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()
