EULAR 31 solution

[david]

Hi. Does anyone have a solution in BASIC for the Eular 31 problem. If you haven't heard of it, it asks "What is the maximum number of different ways you can make up a $ from change"

Clearly, a very similar solution would apply to the British pound!

Many thanks

David

[tsh73]

Brute force way
292 variants

'Number of variants to collect 1$ from coins
'valid coins 1? (i.e. 1 cent or $0.01), 5?, 10?, 25?, 50?

print "num of coins", 50;" ";25;" ";10;" ";5;" ";1
for i = 0 to 2  '50c
   for j = 0 to 4  '25 c
       for k = 0 to 10 '10c
           for l = 0 to 20 '5c
               for m = 0 to 100    '1c
                   sum = i*50+j*25+k*10+l*5+m
                   if sum = 100 then n=n+1: print  n,  i;" ";j;" ";k;" ";l;" ";m
                   if sum >100 then exit for
               next
           next
       next
   next
next


---

Results:
num of coins  50 25 10 5 1
1             0 0 0 0 100
2             0 0 0 1 95
3             0 0 0 2 90
...
290           1 1 2 1 0
291           1 2 0 0 0
292           2 0 0 0 0