Michael,
Here's a possible solution. Since there are no "rules" about choice
of pieces, I wrote an algorithm where we always make a choice at
random. I just keep choosing pieces at random until we get the right
answer or there are no possible choices left. If there are no more
choices, we start over.
This is not an ideal solution for two reasons:
1) It does not detect if there is no possible solution - in which
case it will run forever.
2) It is done at random, so theoretically it could run forever
But despite those warnings, given your set of numbers, this seems to
get to a solution very quickly.
Enjoy,
Irv
on test
lAnswer = findAnswer(315, [13, 27, 35, 48, 90, 111])
sort lAnswer -- pretty up the answer a bit
Alert("And a winning answer is:" && string(lAnswer))
end
on findAnswer targetLength, lPieces
lengthSoFar = 0 -- how much do we have so far
lSolution = [] -- the solution so far
repeat while TRUE
lPossibilities = []
-- look through all pieces
repeat with thisPiece in lPieces
-- if adding this piece matches the target, we're done
if (lengthSoFar + thisPiece) = targetLength then -- Winner!
append(lSolution, thisPiece)
return lSolution
end if
-- if adding this piece still leaves us under the target,
-- add it to a list of possible choices
if (lengthSoFar + thisPiece) < targetLength then
append(lPossibilities, thisPiece)
end if
end repeat
if lPossibilities = [] then -- no choices, then start over
-- put lSolution && lengthSoFar -- for testing
lSolution = []
lengthSoFar = 0
else -- pick next piece at random from possible pieces
nPossibilities = count(lPossibilities)
randomIndex = random(nPossibilities)
randomPiece = lPossibilities[randomIndex]
lengthSoFar = lengthSoFar + randomPiece
append(lSolution, randomPiece)
end if
end repeat
end
At 11:43 PM +0100 2/13/02, Michael von Aichberger wrote:
>Hi everybody,
>
>I'am coding Lingo without really having learned how to program. Sometimes I
>am too dull to figure out how things could best be done.
>
>
>Now that has happened again:
>
>Imagine you had a given length. Like:
>
>length = 315
>
>And you needed to cover that length with smaller pieces. You had a set of
>pieces of a given length, like for instance:
>
>piecesL = [13, 27, 35, 48, 90, 111, ...]
>
>
>Now the algorithm I am looking for should chose any number of the pieces in
>piecesL and add them up the the given length. The pieces can be used several
>times. If the full length cannot be achieved because of the given values,
>the one solution should be found that comes closest.
>
>So I need a solution in the style of
>
>solutionL = [13, 13, 13, 27, 90, 90, ...]
>
>As I said, a question (challenge?) for a "real" programmer.
>
>Asked by a thankful "amateur".
>
>Michael von Aichberger
>
--
Lingo / Director / Shockwave development for all occasions.
(Home-made Lingo cooked up fresh every day just for you.)
[To remove yourself from this list, or to change to digest mode, go to
http://www.penworks.com/lingo-l.cgi To post messages to the list, email
[EMAIL PROTECTED] (Problems, email [EMAIL PROTECTED]). Lingo-L is for
learning and helping with programming Lingo. Thanks!]
