09-26-2004, 09:01 PM
>O_O< Ditto....
.
.
.
.
Mine's still better! It's short =P
.
.
.
.
Mine's still better! It's short =P
Real life problems :)
|
09-26-2004, 09:01 PM
>O_O< Ditto....
. . . . Mine's still better! It's short =P
09-27-2004, 05:26 PM
I regret to let you know that I have no way to make do the testing(!), tangling(?) and fine-tuning(!?!) works of my promised solution optimizer for next few days.
I'm an intern at an outsourcing Turkish game company, and my internship is coming to an end. I've got to deliver my last project on simplifying a "Docking Tool Bar Foundation" in C++. Hey, just prioritizing tasks here!..
Don't interrupt me while I'm interrupting." - Winston S. Churchill
09-27-2004, 06:21 PM
Quote:Mine's still better! It's short =P WT, yours only solved one of the three problems though. So you would expect Toohtooh's and my code to be a lot longer.
09-28-2004, 01:11 AM
Quote:WT, yours only solved one of the three problems though. So you would expect Toohtooh's and my code to be a lot longer. uh eh hmmmm I KNOW YOU WHERE LIVE! *tracerts IP* . . fine but it's still better on some other degree. -_-
09-28-2004, 04:36 PM
Hello! Time for reviews:
ToohTooh: Your sollution has some of the problems that the original DarkPrevail's and Whitetigers': It's a greedy approach. The greedy approach doesn't guarantee that the best sollution is gonna be returned; it doesn't even guarantee that you're gonna get a sollution (you won't ever get a sollution for (100, 75, 52) with amount = 150, when there's one. The greedy approach just tries once, tries to get the best fit at once, and when it finds a sollution it stops trying. DarkPrevail: Your second entry is fairly better. As I understand the code, it tries to calculate every possible combination and then minimize results. That may be feasible for small quantities, but it's terribly slow: it uses brute force. Anyhow, it gets the work done. It looks alot like the iterative version of the backtracking with prune approach (the easiest to code), whose recursive version is the one I'm gonna post when this challenge ends. You can still improve your algo: you can do some pruning , i.e. DO WHILE temp >= v(i) AND coinno < lowest Right now, DarkPrevail is the winner, unless ToohTooh posts the new version or someone else post something better. PS. Moneo, weren't you gonna enter this one?
SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio underBASIC, homegrown musicians [img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
09-28-2004, 06:55 PM
Quote:DarkPrevail: Your second entry is fairly better. As I understand the code, it tries to calculate every possible combination and then minimize results. That may be feasible for small quantities, but it's terribly slow: it uses brute force. Anyhow, it gets the work done. It looks alot like the iterative version of the backtracking with prune approach (the easiest to code), whose recursive version is the one I'm gonna post when this challenge ends. You can still improve your algo: you can do some pruning , i.e. DO WHILE temp >= v(i) AND coinno < lowest You got it man, thats exactly what i was aiming for. I do agree it is not very efficient. I have to say, well done for understanding the code, as I lack the motivation to include comments (lol) and it's not the neatest code ever written. You are certainly correct when it comes to the pruning, i overlooked the fact that it could be made faster with such alterations as that, although i shall not correct it as this is a competition, and you suggested that, so it would be techincally cheating, not to mention the fact I wouldnt be able to locate any more bits to "prune" (i am not very good at code optimisation ;P) Quote:Right now, DarkPrevail is the winner Yay! P.s You should post some more challenges in the future, I enjoyed the challenge posed and your comments were very knowledgeable and had good crit. =)
09-29-2004, 02:04 AM
Also, suppose you had these coins: (11, 10, 2) and you want to total 12. Every solutions so far would start with 11 and then fail.
09-29-2004, 08:16 PM
Sterling, you are correct!
I have modified my code I only needed to change [syntax="qbasic"]IF coinno < lowest THEN[/syntax] to [syntax="qbasic"]IF coinno < lowest AND temp = 0 THEN[/syntax] Now it checks wether it actually finds the correct solution or not. [syntax="qbasic"]DECLARE FUNCTION change% (amount%, v%(), s%()) '$STATIC DEFINT A-Z DIM s(5) 'Please unremark the problem you wish to run: 'This one doesnt need sorted: 'DIM v(5) 'v(0) = 1 'v(1) = 5 'v(2) = 10 'v(3) = 25 'v(4) = 50 'v(5) = 100 'amount = 347 'This one does need sorted: 'DIM v(5) 'v(0) = 10 'v(1) = 50 'v(2) = 1 'v(3) = 100 'v(4) = 25 'v(5) = 5 'amount = 347 'This one can be done more easily than 1x100 + 2x25: 'DIM v(2) 'v(0) = 25 'v(1) = 75 'v(2) = 100 'amount = 150 CLS 'INPUT "Please input the amount to convert to change"; amount coins = change(amount, v(), s()) PRINT : PRINT "Coins required:": PRINT FOR i = UBOUND(v, 1) TO 0 STEP -1 IF s(i) THEN PRINT " "; s(i); v(i); "credit coins" NEXT i PRINT : PRINT coins; "coins in total" FUNCTION change (amount, v(), s()) 'init a little siftsort: FOR i = 1 TO UBOUND(v, 1) FOR j = 0 TO UBOUND(v, 1) - i IF v(j) > v(j + 1) THEN SWAP v(j), v(j + 1) NEXT NEXT lowest = 999 FOR ii = UBOUND(v, 1) TO 0 STEP -1 coinno = 0 temp = amount ERASE s FOR i = ii TO 0 STEP -1 DO WHILE temp >= v(i) temp = temp - v(i) coinno = coinno + 1 s(i) = s(i) + 1 LOOP NEXT IF coinno < lowest AND temp = 0 THEN lowest = coinno lowstart = ii END IF NEXT temp = amount ERASE s coinno = 0 FOR i = lowstart TO 0 STEP -1 DO WHILE temp >= v(i) temp = temp - v(i) coinno = coinno + 1 s(i) = s(i) + 1 LOOP NEXT change = coinno END FUNCTION[/syntax]
09-30-2004, 07:31 PM
Hello again.
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 Code: ' *** 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 Code: FOR i = 1 TO Amount Code: div = i \ ii 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(): Code: minDiv = 1 Code: IF bldThis < 0 THEN bldThis = 0 Code: IF (bldThis >= 0) THEN TECHNICAL: Consider partitions of Amount whose summands are taken (repetitions allowed) from a sequence of integers
For a [4] yielding a
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. Code: ' ***
Don't interrupt me while I'm interrupting." - Winston S. Churchill
10-01-2004, 04:45 PM
To NaThan and Moneo:
I like this real life problem, as it was an exercise at the NIO as well. It was NIO 2004 Exercise I-2 to be exactly. It was then considered to be an 'easy' real life problem, although the exercise at the NIO was quite more difficult that this one, since here you have a set amount of coins and their values are set. In the Exercise I-2 however, a file was used to determine the coins and coin types used (to a maximum of 100 different coins and a maximum value of a coin of 32767). An example of coin input would be (Coins available: {1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}, Calculate best way to pay 7592). The problem was that there was also a time-limit of 10 (?) seconds, so you really had to make a perfect algorithm. Shall I post complete NIO 2004 Exercise I-2 if people are up to a challenge? |
« Next Oldest | Next Newest »
|