FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Calling all programmers!!!





badai
You have this list of 109 numbers:

20
100
500
100
100
1900
100.13
200
200
300
140
100
2700
967.93
100
100
4000
100
100
100
1000
100
200
300
100
200
100
3000
508.47
20
100
100
100
100
2445
462.96
195
1000
300
100
100
20
595.17
250
10
10
3000
668
113.29
1374.68
204.39
697.98
1572.19
253
500
700
500
1100
142.37
2000
475
1850
495
2700
2260.78
500
1270
362.82
1951
444.03
1460
2700
425
2208.98
2700
500
1950
1400
500
2060
2270
1837
2053
751.63
1000
450
1800
1962.93
465
250
2045
300
480
462.87
2470
1514
518.17
3000
2190.93
2600
500
500
500
1004.24
1625
500
2400
2450
780

Write an algorithm to add only 8 of the numbers, and you will get the total of 15629.14.

Any taker?
jmraker
You did not specify whether numbers can be used repeatedly so one solution is
4000 + 4000 + 4000 + 1951 + 508.47 + 444.03 + 362.82 + 362.82

It took my program about 3 minutes to discover that solution.

Posts like this are usually posted in the contest section http://www.frihost.com/forums/vf-11.html
badai
should not use repeatedly, and this is not a contest where i will give any coin or point.

anyway, hundreds others have helped me, so your unwillingness to share does not affect me, beside you are too late.

i hate people who does not share their knowledge no matter how smart they are.

so no thank you.

these are form others:
2445+1572.19+260.78+2270+1962.93+1514+2600+1004.24

most gave the algorithm, some gave the full program, few even helped convert their program to php. and none of them have to figure out that you can use those numbers more than once, because if you do, you don't even have to write any program. just take a look at the list, and pick the biggest followed by smaller to add up.

smart ehh?

where the program by the way?
jmraker
I took the numbers, removed the duplicates, sorted by largest first and did an 8 level loop. The more numbers in the list the longer it takes to go through it. Did you get a good grade?

Code:
<?php
$find = 15629.14;
$numbers = "4000
3000
2700
2600
2470
2450
2445
2400
2270
2260.78
2208.98
2190.93
2060
2053
2045
2000
1962.93
1951
1950
1900
1850
1837
1800
1625
1572.19
1514
1460
1400
1374.68
1270
1100
1004.24
1000
967.93
780
751.63
700
697.98
668
595.17
518.17
508.47
500
495
480
475
465
462.96
462.87
450
444.03
425
362.82
300
253
250
204.39
200
195
142.37
140
113.29
100.13
100
20
10";

$numbers = explode("\n", $numbers);
foreach($numbers as $k=>$v)
   $numbers[$k] = (float)trim($v);

foreach($numbers as $v1){
   echo "\n";
   foreach($numbers as $v2){
      echo '.';
      foreach($numbers as $v2){
         foreach($numbers as $v3){
            foreach($numbers as $v4){
               foreach($numbers as $v5){
                  foreach($numbers as $v6){
                     foreach($numbers as $v7){
                        foreach($numbers as $v8){
                           $tot = $v1 + $v2 + $v3 + $v4 + $v5 + $v6 + $v7 + $v8;
                           if($tot == $find){
                              var_dump($v1, $v2, $v3, $v4, $v5, $v6, $v7, $v8);
                              die('Solved');
                           }
//                           else echo $tot . "\n";
                        }
                     }
                  }
               }
            }
         }
      }
   }
}
die('Failed');
?>
jajarvin
badai wrote:
Write an algorithm to add only 8 of the numbers, and you will get the total of 15629.14.

jmraker wrote:
I took the numbers, removed the duplicates, sorted by largest first and did an 8 level loop. The more numbers in the list the longer it takes to go through it.


But when we have for example we have total 10 000 numbers and we have to find for example 500 numbers
so that their sum is 15629.14?
There would be 500 loops in a PHP-program Exclamation

So I wonder is there maybe another algorithm for this problem so
that the program which is based on this algorithm would be a little bit simple than jmraker's solution Question

I am trying to find such an algorithm which is base on graphs.
If we think that the numbers are nodes of a graph so the solution of
this problem is to find a path which contains such 500 nodes(numbers) so that
their sum is 15629.14.
I am still working with this algorithm of mine. Very Happy
jmraker
If there was 10,000 numbers in the list it would be closer to 100,000,000,000,000,000,000,000,000,000,000 loops (less than 10,000^Cool

Since I knew the solution would involve several large numbers it starts off with the largest first so most of the loops don't have to go through the list too much. It could have taken hours or days if the 8-number total it was looking for was smaller.

If I wanted to optimize it, I'd start by adding logic in every loop, checking if a sub-total was over that number would help reduce the number of loops like in the 2nd loop if it's at 4000+3000 and it goes over, it skips the additional loops and tries 4000+2700 and 4000+2600 until it's under, then it goes into the 3rd loop and tries 4000+2600+2470. Every time it skips a loop it saves a lot of wasted time.
Related topics
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.