Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: How to find which of fifty numers yield a sum
Replies: 10   Last Post: Oct 25, 2000 4:20 PM

 Messages: [ Previous | Next ]
 Joe Ascoly Posts: 23 Registered: 12/13/04
Re: How to find which of fifty numers yield a sum
Posted: Oct 25, 2000 1:46 PM

--------
-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.
-

Date Subject Author
10/19/00 David Ball
10/20/00 Dave Ashley
10/20/00 Ulrich Elsner
10/20/00 Peter L. Montgomery
10/20/00 Andres Asensio Ramos
10/21/00 Serge Kanilo
10/22/00 Nabeel Azar
10/23/00 David Ball
10/24/00 Nabeel Azar
10/25/00 Joe Ascoly
10/25/00 Nabeel Azar