Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: How to find which of fifty numers yield a sum
Posted:
Oct 25, 2000 1:46 PM


Here are some comments about this problem posted by David Ball. And a comment about the reply posted by Nabeel.  David Ball wrote: Hi, Suppose you have fifty numbers related to money, such as $23.56,$167.56, $35,79, 72.70, etc. Is is known that a subset of them sum to x. Is it possible to determine which numbers sum to x? What if there were hundreds of numbers to look at?  A set of 50 numbers were generated and treated as integers rather than dollars and cents. The following table generated from a set of 50 numbers shows that if you had find the items that sum up to 700 you would need to search 2 groups addup 3 at a time and 4 at a time. The total search would be the sum of 19,600 and 230,300 The larger the number the more you have to search. If the Total is greater than 130,456 no search is necessary. I believe that this is a case of nested do loops to find the items that total to a given amount, and the table below shows how to limit the search to a subset of all possible.  n low hi search  1 39 4956 50 2 212 9869 1225 3 448 14543 19600 4 686 19196 230300 5 954 23748 2118760 6 1289 28172 15890700 7 1653 32403 99884400 8 2113 36558 536878650 9 2771 40391 2505433700 10 3866 44202 10272278170 11 5102 47985 37353738800 12 6415 51764 121399651100 13 7779 55531 354860518600 14 9421 59212 937845656300 15 11248 62826 2250829575120 16 13166 66332 4923689695575 17 15246 69766 9847379391150 18 17334 73163 18053528883775 19 19517 76558 30405943383200 20 21811 79914 47129212243960 21 24200 83184 67327446062800 22 26798 86442 88749815264600 23 29433 89606 108043253365600 24 32082 92765 121548660036300 25 34746 95710 126410606437752 26 37691 98374 121548660036300 27 40850 101023 108043253365600 28 44014 103658 88749815264600 29 47272 106256 67327446062800 30 50542 108645 47129212243960 31 53898 110939 30405943383200 32 57293 113122 18053528883775 33 60690 115210 9847379391150 34 64124 117290 4923689695575 35 67630 119208 2250829575120 36 71244 121035 937845656300 37 74925 122677 354860518600 38 78692 124041 121399651100 39 82471 125354 37353738800 40 86254 126590 10272278170 41 90065 127685 2505433700 42 93898 128343 536878650 43 98053 128803 99884400 44 102284 129167 15890700 45 106708 129502 2118760 46 111260 129770 230300 47 115913 130008 19600 48 120587 130244 1225 49 125500 130417 50 50 130456 130456 1   Contents of S is sorted list of 50 numbers selected at random from 1 5000 S 39 173 236 238 268 335 364 460 658 1095 1236 1313 1364 1642 1827 1918 2080 2088 2183 2294 2389 2598 2635 2649 2664 2945 3159 3164 3258 3270 3356 3395 3397 3434 3506 3614 3681 3767 3779 3783 3811 3833 4155 4231 4424 4552 4653 4674 4913 4956 Here is an APL call to ch2 a function that finds pairs in S 212 CH2 S * CHECK PAIRS OF 2 FOR 212 NUMBER OF SUMS IS: 2 39 173 173 39
  about the posted problem Nabeel wrote: Hi Dave, Actually, the contest aim wasn't to fit a certain number of songs on a CD. Given a CD's length in minutes, the aim was to select from a pool of songs ones to put on a CD to minimize the unused CD time. A simple example: CD playtime 10 minutes. songs: 7 min, 2 min, 5 min, 1 min.  Ascoly reply: There is 1 way to fit the cd with 2 songs at a time 5,5. There are 6 ways to fit 3 at a time 721,712,271,217,172,127 and 16 ways to fit the cd with 4 songs. 



