Determine the maximum value that is obtained by multiplying together a set of positive integers which are all different and whose sum is 70.

DECLARE SUB try (s#)
DEFDBL A-Z
DIM SHARED maxprod, maxnum, maxset(11), prodnow, totnow, numnow, setnow(11)
DIM SHARED ct, ct2

FOR i = 1 TO 70
 numnow = 1
 totnow = i
 prodnow = i
 setnow(1) = i
 try 2
NEXT i

PRINT ct
PRINT maxnum; maxprod
FOR i = 1 TO maxnum
 PRINT maxset(i);
NEXT
PRINT

PRINT ct2

SUB try (s)
 IF totnow = 70 THEN
  ct = ct + 1
  IF prodnow = 68428800 THEN ct2 = ct2 + 1
  IF prodnow > maxprod THEN
    maxnum = numnow
    FOR i = 1 TO maxnum
      maxset(i) = setnow(i)
    NEXT
    maxprod = prodnow
  END IF
 ELSE
  FOR i = setnow(s - 1) + 1 TO 70 - totnow
    numnow = s
    setnow(s) = i
    prodnow = prodnow * i
    totnow = totnow + i
    try s + 1
    totnow = totnow - i
    prodnow = prodnow / i
    numnow = s - 1
  NEXT i
 END IF
END SUB

finds

 29927
 10  68428800
 2  3  4  5  6  8  9  10  11  12
 1
 
indicating:

 29,927 ways of selecting unique integers adding to 70.
 
The maximum product uses  10 integers and that product is 68,428,800.

The integers  2  3  4  5  6  8  9  10  11  12 do this.

There is only 1 way of choosing integers multiplying out to 68,428,800 -- the integers shown.

(The line

  IF prodnow = 68428800 THEN ct2 = ct2 + 1
 
 was added after that maximum was found on a previous run.)

Posted by Charlie on 2009-10-30 12:28:16