Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
Ed Wall
Posts:
36
Registered:
12/3/04
|
|
Re: Combinatorics Problem
Posted:
Feb 25, 1996 1:03 AM
|
|
>A question that I posed to a colleague, and passed onto the list, was the
>task of splitting a set of 200 numbers into two sets that had the same sum.
>
>I claimed that it is unsolvable, in practice, since there is no efficient
>algorithm, other than testing a huge number of cases (I suggested on the
>order of 200 C 100).
>
>Two of the respondents have indicated that this problem is NP-Complete, and
>hence the number of operations rises exponentially compared to the number of
>values given. Given this, for a large enough set, the problem is
>effectively unsolvable. So the question becomes, is 200 values sufficiently
>large?
>
>Here is the test.
>
>The number below have a total of 10 000 000. Can you split it into two sets
>that each have a sum of 5 000 000? I generated this list using Excel, so
>there _is_ an answer, that currently only I know. Shane, me old mate, good
>luck!
>
>BTW, this whole thing arose out of a grade 8 problem on putting 9 songs onto
>the two sides of a cassette tape.
>
>Cheers
>
>Rex
>
Nmbers deleted
Hi Rex
Well, it took less than a second what with putting the stuff on
the screen. However, I don't have the right answer it seems. Optimization
probs are like that sometimes because of the algorithm. One problem might be
I don't switch unless I improve an estimate. It would be interesting to see
if this is indeed the problem, but probably I need to sit down and think about
the math. Enclosed are my numbers.
Ed Wall
P.S. This was on an old 386 33Mhz.
First Set 50000048
983622 971689 962789 959667
933821 929619 918711 916610
902232 883615 875136 874892
843620 826754 795978 776007
768012 762929 747714 747146
732684 728239 723171 706320
675889 661992 659526 657999
630451 625483 603458 594598
591086 576808 566380 553768
541300 522265 514524 510891
490452 480863 479702 470791
455672 420380 405208 403834
387869 373825 371936 363255
353054 350076 323841 323287
306082 303653 291891 278911
273244 271445 270345 249402
242224 226486 220428 188895
160968 132459 124377 118006
98758 92364 90151 78736
49719 44789 34673 18569
Second Set 49999952
980623 973351 967401 948298
936671 926805 921325 911686
904135 883780 880661 878786
842729 819084 777567 776612
768280 766406 760202 746189
730590 727062 723825 722232
672489 661236 658188 651260
629646 610398 608278 600021
584669 583903 563398 554680
535084 534640 511926 510680
491163 489897 478824 470666
440091 426247 419923 402549
380315 376348 372344 369254
350464 341102 333189 320702
309478 301115 287872 282512
276728 271504 260305 260234
236846 234213 212595 194564
155635 152976 121418 114794
94912 90490 85026 83528
61794 43182 32701 8119
|
|
|
|
