Å bygge høye tårn.

[Nebuchadnezzar]

Håper Aleks, Vektormannen, Plutarco eller andre som har en neve peiling på programmering kan
hjelpe meg her. Fikk denne "nøtten" av kompis, og tenkte det kunne være artig å prøve. Selv om
programmerings-ferdighetene mine er nokså skrale.

Du er den siste tårnbyggeren i et land overtatt av kommunisme. For at du skal beholde livet må
du bygge $m$ tårn av ett sett med byggesteiner $v$. Ett grunnleggende prisnipp i kommunstland er
likestilling. Tårnene må altså ha så lik høyde som mulig (ett enkelt mål er å ta standardaviket)

Funksjonen skal altså ta inn antall tårn m og $n$ byggesteienene som ligger i en vektor v.
For eksempel la oss si at du skal bygge 3 tårn med byggesteinene $1,2,3,4,5,6,7,8,9$. Her er du
heldig, da en løsning er

$ \hspace{1cm}
\begin{pmatrix}
2 & 7 & 6 \\
9 & 5 & 1 \\
4 & 3 & 8
\end{pmatrix}
$

hvor en visualiserer seg at tårnene står som på diagrammet her http://www.jamesegrantcpapc.com/images/histogram.jpg.

Jeg klarer problemet for små vektorer. Men hva vil en effektiv måte være for en stor vektor v http://pastebin.com/ybAYGHns?
Si for 500 , 333, 250 og 43 tårn?

[Nebuchadnezzar]

Fant hvertfall en eller to mulige løsninger. Aner fortsatt ikke hvordan en kan bestemme den optimale metoden
å bruke på ulike datasett. Ingen av metodene er optimale, selv om tilfeldig gir beste løsning for små vektorer.

Standard Grådighet

http://pastebin.com/9EWE2TL7

1. Sorterer brikkene fra størst til minst
2. Bygger opp tårnene en brikke av gangen.
Det minste tårnet får alltid neste brikke

Modifisert Grådighet

http://pastebin.com/fqKyE1zT

Kompis som foreslå denne metoden. Ser ut som den fortsatt har $O(n)$ kjøretid.

0. Sorter brikkene fra størst til minst
1. Bygg opp ett og ett tårn til rett før du når taket.
Taket er hvor mange brikker et tårn gjennosnittlig skal ha. Tak = sum( brikker ) / antallTårn
2. Bruk grådighet på de gjennværende elementene. Vi legger altså til
den største brikken til det minste tårnet. Frem til en går tom for brikker.

Tilfeldig

Som en siste metode laget jeg meg bare en tilfeldig matrise og itererte over den.
DEnne metoden var latterlig bra for små matriser, og bra for store matriser. Siden metoden
ovenfor er rask, men ikke så rask..

[Vaktmester]

Hvorfor er ikke dette problemet i NP? Synes det ligner veldig på Knapsack-problemet...

Jeg ville forøvrig brukt en constraint-solver for å løse det. Muligens det er juks :-)

[Nebuchadnezzar]

Problemet er vel NP hardt ja. Og Knapsack problemet hadde jeg ikke hørt om før
men klarte å lese meg litt opp på det. Likner relativt mye ja. Bare at her er målet å få
sekkene likest mulig hverandre, under en gitt grense. Her er det ikke noen slik grense

Hvordan ville du angrepet problemet med "constraint-solver" for å løse det?

[Vaktmester]

Er litt opptatt i dag - skal prøve å kode opp en løsning i løpet av morgendagen. :-) Må innrømme at jeg leste først oppgaven som at tårnene skulle være like - det blir litt vanskligere når man skal minimere standardavviket, men det går..

[Aleks855]

Er litt opptatt i dag - skal prøve å kode opp en løsning i løpet av morgendagen. Må innrømme at jeg leste først oppgaven som at tårnene skulle være like - det blir litt vanskligere når man skal minimere standardavviket, men det går..

Minste kvadraters metode?

[Nebuchadnezzar]

Mål gjerne standardaviket du får for disse tre vektorene

http://pastebin.com/aWavj5df

http://pastebin.com/LZD4cYNv

http://pastebin.com/9UcijnmP

Alle har lengde 1000, og det skal respektivt bygges 2, 3 og 23 tårn. Sånn en har sammenlikningsgrunnlag ^^
For å sammenlikne fikk jeg følgende standardavik [0,17,30] på de tre vektorene.

[Vaktmester]

Ser ikke ut som min løsning er raskt nok til å løse den siste oppgaven. Men det er kanskje noe av poenget med hele oppgaven - at den er så vanskelig at brute force blir umulig, så man er nødt til å gjøre noe smart...

Bruker forøvrig biblioteket google or-tools.

Koden: I tilfelle noen er interessert i en løsning som ikke fungerte :-)

Kode: Velg alt

# -*- coding: utf-8 -*-
from ortools.constraint_solver import pywrapcp

def main(blocks, n):
    solver = pywrapcp.Solver('tower')

    h = [solver.IntVar(0, 100000000000,"h(%i)"%i) for i in range(n)]  # høydene til alle tårnene
    quad = [solver.IntVar(0, 1000000000000,"q(%i)"%i) for i in range(n)] # (h - avg)^2 for alle tårnene
    avg = solver.IntVar(0, 1000000000000,"avg") # gjennomsnittlig høyde
    var = solver.IntVar(0, 100000000000000,"var") # variansen

    towers = [[solver.IntVar(0,1,"x(%i,%i)"%(j,i)) for i in range(len(blocks))] for j in range(n)]
    flat_towers = [block  for one_tower in towers for block in one_tower]

    #  en blokk kan bare brukes en gang...
    for i in range(len(blocks)):
        same_block = [towers[j][i] for j in range(n)]
        solver.Add(solver.Sum(same_block) == 1)

    # finner høydene til tårnene
    for i in range(n):
        solver.Add(h[i] >0)
        solver.Add(solver.ScalProd(towers[i], blocks) ==h[i])

    #finner gjennomsnittshøyden
    solver.Add(avg * n  + solver.Sum(h)%n ==  solver.Sum(h) )

    for i in range(n):
        solver.Add(quad[i] == (h[i] - avg)*(h[i] - avg))

    # og variansen
    solver.Add(var == solver.Sum(quad))

    # objective

    objective = solver.Minimize(var,1)

    #
    # solution and search
    #
    solution = solver.Assignment()
    solution.Add(flat_towers)
    db = solver.Phase(flat_towers,
                      solver.CHOOSE_RANDOM,
                      solver.ASSIGN_MAX_VALUE
    )

    solver.NewSearch(db,[objective])

    num_solutions = 0

    while solver.NextSolution():

        print "var: ", var, "   avg: ", avg

        for t in range(n):
            print h[t].Value(),": ", [blocks[i] for i in range(len(blocks)) if towers[t][i].Value()]
        print
        num_solutions += 1
    solver.EndSearch()

    print
    print "num_solutions:", num_solutions
    print "failures:", solver.Failures()
    print "branches:", solver.Branches()
    print "WallTime:", solver.WallTime()

#site 1
n= 2
blocks = [425,709,704,891,152,805,208, 74,807,214,471,265,250,820,153,168,308,342,612,836,845,793,968,155, 30,377,129, 79,622,136,579,247,756,355, 80,590,335,688,940,780,669,758,482,464,939,617,316,341,863,945,982,621,286,833,673, 70,268,185,205,366,766,619,254,966,926,781,740,898,228,497,705,747, 28,678, 94,503,478,524, 23,599,499,403,603,846,119,274,726,753,706,338,191,776,267,261,212,743,373,344,818, 83,294,745,799,715,452, 32,455,666,654,218,112,500,246,624,917,264,421,597,127,895,525, 50,363,339,802,708, 14,429,679,465,484, 69,298,241,516,303,911,604,220,369, 81,873,116,401,661,337,779,762,390,627,912,189,501,881,507,485,378,924,975,555,126,858,109,539,914,804,955,187, 19,481,976,613,751,237,967,963,544,292,102,746,593,668,674,958,736, 62,463,124,879,675,131,346,211,520, 59,238,959,925,717,291,828,243,418,232,144,505,167,732,629,680, 92,413, 42,258,862,312,908,956,657,467, 66,142,996,530,841,852, 55,819,190,606,572,712,  5,449, 76,872,552,193,528,941,209,388,137,445,801,396,947,916,466,931, 60,554,227,486,651,974,289, 90,132,161,913, 51, 24,640,923,537,857,962,419,181,108,204,727,595,106,936,115,270,352,333, 58,110, 82,535,504,957,518,343,871,849,813,748,903,360,671,739,182,615,944,440, 17,847,407, 35,574,646,154,376,543,556,134, 68,649,534,919, 48,973,608,837,456,660,313,775, 43,493,691,665,196,332, 15,370,201,633, 21,876,639,296,783,130,540,653,385,272, 93,616,287,424, 53,236,340,983,817,981,105,527,575,838, 96,735,721,304,991,951,384,149,402,821, 37,877,375,391,722, 22,300,829,954,280,459,290,231, 49,173,694,315,488,888, 18,310,215,150, 31,978,928,839,759,663,480,605,420,850,327, 65,808,  2,408,921,183,929,786,371,844,565,789, 52,361,750,800,628, 13,784,724,894,562,693,436,356,284,814,285,707,977, 89,146,634,350, 71,216,964,699,655,623,720,861,770,141, 40,412,906,242,169,213,710,461,952,647,322,336,965,652,273,454,884,741,000,725, 27,869,164,788,411,803,950,509,195,367,423,122,100, 47,120,  7,902,598,812,271,203,582,222,430,749,251,405,773,317,765,324,659,138,410,815,394,522,602,927,792,496,433,226,446, 97, 57,868,601,949,492,993,645,854,811,498,532,806,744,865,282,121,325,278,538,842,658,199,474, 84, 41,458,256,180,123,200,513,531,764,832,910,878,810,415,672, 85,676,825,700,179, 54,166,569,855, 86,194,457,160,117,550,358,348,594,729,240, 39,664,305,260,514,521,892,244,934,683,752,899,831,896,874,479,314,592,219,279,561,564,224,946,253,140,114,437,768, 95,798, 16, 61,197,690,147,642,252, 64,301,581,571,714,961,380,681,589,502,427,523,785,920,738, 11,856,611,288,987,809,165,795,999,223,626,576, 98,239,103,379,563,840,897,359,328,383,969,638,381,998,235,397,536,362, 73,716,620,229,353,248,460,994,393,128, 91,937,830,882,511,320,  8,416,697,515,113,519, 34,698,323,148,763,389,915,283,618,171,777,428,557,349,529,718,281,409,206,757,632, 77,177,824,354,687,560, 56, 99,625,631,584, 72,439,447,737,566,490,512,985,984,656,559,470,684,  4,  1,299,883,885,202,585,406,577,867,255,526,682,890,392,935,259,637,918,487,309,848,685,583,364,843,245,887,443,553,175,835,542,495,125,163, 25,249,643,145,345,719,591,573,960,990,701,198,257, 26,489,477, 33,689,451,221, 38,101,570,143,277,372,395,157,414,468,614,188,444,790,989, 45, 20,186,686,548, 87,794,506,207,864,630,438,979, 75, 29,909,782,263,234,306,404,791,771,702,311,104,713,321,162, 12,111,547,374,533,510,  9,107,970,266,176,870,587,269,971,568,462, 67,662,853,860,472,275,816,368, 78,772, 88,326,432, 36,172,728,859,417,295,382,822,600,826,426,986,730, 63,767,387,827,  3,635,422,133,938,904,541,769,276,711,473,351,901,334,834, 46,331,610,386,329,434,677,545,262,442,318,178,475,567,580,483,453,225,293,905,695,761,549,398,517,184,578,796,932,907,886,667,948,943,546,930,596,118,650,734,893,558,648,980,997,933,889,900,696,588,636,170,551,307,851,448,778,731,703,435,491,192,  6,644,158,494,319,469,742,297,953,230, 44,995,972,400, 10,866,670,992,156,431,508,875,357,609,159,217,586,607,922,347,450,988,210,755,330,641,233,139,135,302,880,787,692,754,823,760,797,723,365,441,942,399,476,174,774,151,733]
# site 2
#n=3
#blocks=[1022, 486,1003, 955, 582, 314, 742,1008,   0, 711, 885, 806, 805, 624, 382,   0,1081, 229, 726, 644, 712, 941, 799, 921,1059, 237, 453,   0, 913, 862,1021,   0, 621, 454, 476, 262, 714, 903,   0, 925, 805, 462,1102,1092, 231, 929, 707, 378,1134,1177,1048, 563, 619, 547, 809, 552, 246, 890, 683, 986, 746, 776,   0,   0, 957, 393, 209,   0, 609, 416, 271,1125, 437, 793, 402, 863,1106, 205, 585,1138, 657, 248, 641, 345, 232, 616, 715, 414, 680,1126,   0, 981,1051, 919,1134, 207, 540, 536,1113, 797, 428, 957, 614,   0, 815, 581, 855,1066, 679,1107,1111,1180, 835,   0, 219, 451, 254,1020, 604,1099, 267, 247, 440, 298, 493,   0, 424,1147, 631,1064, 204, 585, 740,1117, 882, 212, 258, 539, 697,1054, 984, 670, 439, 925,1087,   0, 659, 855, 982, 707, 421,   0, 982, 777,1107,1108, 599, 256, 886, 604, 966, 804, 505, 483, 600, 969, 837, 383,   0, 244,   0,   0,1002, 304, 754, 866,1160,   0,   0, 549,1161,1095,1066, 470, 643,   0, 585, 906, 426, 469, 282, 623, 220,1100, 806, 859, 808, 794, 866, 269, 337,1167,1186, 549, 236, 887, 744, 786, 670, 568, 252, 225,1152, 408, 239, 784,1081, 773, 613, 993, 722, 711,1182, 378, 512, 586, 345,   0, 373, 432, 424, 361, 606,1025,1093, 940, 234, 781, 838, 444, 447,1047, 557, 413, 230,   0,1061, 748,1035,1024, 455, 302, 555, 230, 447, 380, 689, 940, 720, 953, 395, 914,1129, 649,1021, 629,   0,1014, 548, 726, 862,1152, 956, 854, 839, 801, 791, 336,1042,   0, 454, 532, 931, 425,1024, 608,1041,   0, 777,1147,1103,   0, 492, 416, 313, 842, 894, 210, 903,1039, 413, 553, 760,1031, 279, 957,   0, 669, 749, 706, 955, 972,   0, 311, 454,   0, 948, 767,1128, 527,   0, 757, 278,1046, 959, 845, 537, 695, 657, 258,1128, 388,1077,1169,1179, 473, 750, 424, 676,1163,1112, 793, 386, 236,1038,1179,1138, 308, 423, 946, 652, 847, 960, 289, 555, 682, 476, 837, 910,1009, 243, 418, 899, 596,   0, 962, 247,1179, 267, 215,1023,1188, 968, 936, 527,   0,1074, 445,1009,   0, 834, 346, 933, 450,1085, 427,1066, 215, 234, 619, 536, 323,1070, 639, 647,1118, 236, 363, 771,   0, 875, 418, 810,1154, 614,   0, 695, 962, 682,1115, 469, 233,1068,1027, 792, 855, 358, 628, 428, 407, 309, 262, 689, 839, 267,   0,   0, 607,1129, 534, 317, 338, 334, 861, 913, 965, 753, 628, 849,1161, 982,1026, 804, 990, 596, 610, 864, 437, 311, 463,1196,1130, 270, 439,1036, 303, 638, 526, 234, 286,1103,1116,   0, 767,   0, 210, 720,1044, 561,1152,   0, 355, 620, 401, 891, 995,   0, 236, 987, 220, 790, 854,   0, 353, 240, 964, 776,   0, 527, 614, 222,1083, 481, 524, 987, 213, 680,1014, 234, 531,   0, 360, 466,   0, 341, 871, 310,   0, 899, 384, 839, 953, 816, 776, 380, 736, 628, 464, 896, 924, 606, 448,1181, 564, 400,1108,1049, 751, 368,1034, 603,   0,   0, 840, 281, 453, 425, 676, 692, 507,   0, 409, 818,1166,1068,1146,   0, 654, 739,   0,   0,   0, 406,1197,1119, 802, 685, 226, 575,   0, 250, 559, 379, 330,1120,1092,1025,1102,   0, 662,1167, 470,1089, 274, 399, 979,1089, 512, 432, 345, 989,1081, 511, 567, 308, 208, 346, 731, 324, 921,1200, 261,1177,1141, 365,1148, 524,   0, 540, 572,1041, 718, 716, 664, 339, 459, 784,   0, 704,1106,1124, 747, 248, 312, 434, 824, 773, 762, 235,1000,1065, 215, 579, 942,1054,1179, 482,1120,1138, 441, 862, 785, 747, 288, 872,   0, 792, 475,1128, 870, 793,1143, 803,1095, 400, 928, 577,   0,   0,   0, 752, 784,1165,   0, 387,   0,   0,1004, 704, 709,1163, 738,   0, 815, 781, 984, 438,1105, 952,   0, 419, 531, 492, 718,1143,   0, 322, 590, 835, 336, 609, 952,1087, 505, 828, 829,   0, 347,   0, 563, 867, 876, 291,   0, 652, 488,1180, 450, 824,1132, 622,1145, 324, 603,   0,   0, 625, 301, 586, 261, 725, 760, 777,   0, 621,   0, 932, 979, 269,1169, 981, 232,   0,1169,0000, 957, 773, 560, 643, 829, 490, 629, 506, 348,1090, 542, 507, 568,   0,   0,1046, 892,1160, 817, 866, 732, 640,1057, 666,   0, 377, 423, 747, 603,   0,1048, 616,   0,1117,1183, 325, 781, 530, 381, 829,1004, 666, 858, 600, 870, 439, 539, 286, 806, 869, 286, 931, 720, 659,   0, 931, 395, 849, 327, 992, 888, 278, 776,1011,   0, 811, 836, 250,1126, 900, 583, 764, 386, 921, 799, 757, 638, 979,   0,1194, 528, 802, 727, 856, 257, 566, 640,   0, 722, 828, 217,1058, 459, 394, 212,1173, 698, 909, 417, 654,   0, 956, 551,1078, 402, 213, 386, 278, 812, 370, 282, 438, 952, 354, 648,1130, 974, 827, 591, 836, 648, 696,   0, 898,   0,1195, 712, 665, 708, 560,1046,1183, 245,   0, 288,1020, 405, 974,1013, 226,1030, 563, 417, 433,   0, 917, 693, 348, 669, 361,1058, 563, 881,1011, 620, 708, 307,1150, 648,1153, 646,1196, 824, 892, 713, 584,   0, 868, 953, 681, 896,1137, 735,1124,1199,1122, 911,   0,1020,1037, 325, 227, 520,1177, 624, 966, 874, 835,1042, 994, 375,   0, 411, 421,1148, 732, 934,   0,   0,1037, 972,1036, 874, 937, 475, 530, 547, 308, 896,   0, 413,1033,1159, 379,1121, 306, 738, 914,   0, 867,   0, 398, 795,1018, 510, 942, 376, 915, 521, 401, 462, 217,1081, 423,   0, 486, 865, 832, 759, 629, 831, 654, 992, 409,1146,   0, 371, 787, 720, 647, 905, 446, 817, 636,1014, 817, 294,1196,   0, 701, 243, 571,1054, 327, 587, 245,1046, 453, 509,1119, 412, 206, 734, 959, 729]


#site 3
#n=23
#blocks = [2008,7533,650,9022,1634,9978,5565,8519,9269,5193,5484,2434,3008,5286,1744,8837,3531,6080,3147,4929,6319,3396,1914,6680,4015,8774,6882,3909,63,4580,6662,6442,1094,5254,1773,1389,5605,2623,6549,5840,2192,1704,7923,576,2403,8289,297,5323,8406,7344,4052,4081,4448,5082,5492,9677,8447,5309,8972,1452,9937,9467,2441,4190,2845,1166,3477,2288,5487,3929,2614,9896,4959,4191,8859,4332,3300,5693,3447,4439,4711,2956,533,9099,1688,4059,450,780,5554,9934,799,9711,6131,8500,4259,5421,9777,9246,2915,5308,7408,7385,3415,234,6257,2602,8627,2933,6838,1287,3368,1777,1765,4458,4079,4031,3452,441,2939,9324,7802,7636,5152,2387,673,2900,5734,7064,8788,9487,7380,5767,7423,7510,8505,9450,6215,8406,7545,6081,6161,1405,999,3265,2480,6237,3331,1515,441,897,708,5873,808,1130,6204,8985,1729,3906,4351,7084,9413,3656,62,7618,7622,7284,1326,5585,6435,4865,9393,7600,6353,5001,4289,7771,8076,2653,3949,2920,9252,4158,6278,3303,306,5184,1068,2275,6328,7553,7818,1349,6552,4116,4039,4961,909,417,7066,8721,292,4737,4147,8960,1408,5305,1876,544,6100,9640,9857,4056,7167,1,9861,7979,3560,6224,7241,3230,691,7629,46,7104,1293,5012,7942,3446,264,7988,6076,7986,9779,7931,4245,2180,8703,7695,9396,9555,5730,4334,2526,8203,4828,6065,125,4823,3631,2516,3916,4101,1036,3326,8992,5252,2192,8050,6975,441,9265,8201,4129,3011,309,7236,5859,7303,9850,5348,5443,8527,7556,3602,3335,5937,9811,201,4004,4632,5122,9174,1,9715,7906,7955,2200,4105,4429,2197,8922,7073,506,1,136,8106,8952,7814,2513,5293,9968,6564,9632,1229,9969,4399,5507,45,4804,5216,3469,3121,2502,7199,7972,5594,8853,4600,9922,7508,3714,6430,2140,4421,2219,2626,7498,6984,6300,3780,1602,284,1,4984,1414,1710,1528,9901,1433,4229,7014,8913,6262,6967,980,1611,4688,8702,6955,6225,1697,8402,3610,6811,4322,9741,9284,1456,895,4409,5169,4783,377,1647,8663,7932,3220,812,1656,4573,5545,3866,5853,5764,4248,1776,1,2997,7981,5922,9363,9035,9182,1019,1519,8341,2931,457,7807,7360,2238,4145,7184,7406,1,4810,3171,1239,2527,1029,3,6467,2638,1,-3,2576,3679,5579,7112,4011,6038,4984,2498,1935,3359,5472,8129,5276,810,8714,3212,1,5011,7069,3189,8950,1123,1,500,4133,9106,4190,5263,513,1342,7507,9140,4539,8555,4181,1441,2748,7426,7153,8535,6782,2562,4681,990,1510,1250,9618,6440,2654,841,3841,7336,7462,5938,4363,1,657,6177,4344,3597,455,745,7948,4291,1557,1092,3055,3630,9196,8799,1207,8276,9654,1801,9628,5297,1173,594,6119,8720,9992,4071,7424,6148,5418,9202,6654,246,2628,7317,2668,6111,1988,2623,8271,6871,2412,746,3636,3597,9797,1166,907,4838,1885,3667,9621,4487,9171,8382,8942,1366,1594,4587,6457,4821,9540,8334,9504,3839,9969,5196,4390,6613,1,6205,9231,2384,5193,582,7713,3086,4252,9587,4052,-5,1158,8423,4662,1370,5808,4886,6607,1625,2968,5725,8776,5434,873,4649,185,2916,4375,6528,9547,9872,5192,5626,9827,4889,4910,6252,9733,5987,2943,5622,5542,1084,9064,1,274,553,2516,3499,4738,4965,7661,9032,756,9281,9396,426,5116,6227,597,2614,3277,2042,7742,2901,9041,8866,6239,8588,8727,4250,670,4657,3881,4583,4043,9346,2708,5419,1188,945,3165,1444,8868,3318,9335,5353,3107,8557,9344,5465,558,5649,1010,3923,1,7247,7739,7474,2400,9919,8629,8945,4510,5098,6846,4411,2008,4200,4994,1281,6842,6446,2701,5286,791,7538,7738,3926,2864,4638,7776,2129,8957,1379,1,2215,9309,4065,9383,6538,1,4203,5441,8399,1196,8287,6283,8347,2305,5293,5105,8817,4888,196,6699,3710,9332,7559,2191,5888,8813,7113,7504,7355,2463,4107,4969,5988,3870,4015,3904,806,8534,3178,5980,8673,3079,1013,4036,7902,2051,247,8435,9124,6833,1890,6399,6963,2686,1233,9072,1624,3023,8102,2779,8664,5105,2266,5110,5048,2883,2299,3895,860,3995,6309,2951,523,1042,2314,3168,2088,4225,6161,3719,1054,5601,9037,4317,9156,1712,7504,953,1087,2589,9696,2240,4506,5977,5073,3002,3613,6006,963,8137,5783,3685,9489,8032,3607,4545,5963,6545,7828,2687,4396,4915,4442,4752,4329,1537,3111,6173,2820,6967,4630,1390,8669,1593,9602,988,8787,3291,8574,4521,5007,2947,190,7863,3269,7335,7052,4494,740,1,8406,3958,2369,2824,8327,4934,6623,2099,7076,1882,7097,657,593,585,7985,2426,9623,6404,7284,539,3602,1304,710,2217,558,2093,3085,6273,9821,8836,6681,5988,7839,3260,9268,2762,3907,6605,1,2870,3358,762,210,2028,9269,6206,4821,7223,3986,1471,1872,9575,464,3678,8220,4784,6028,8366,6302,4097,9266,6713,7431,9583,2957,7918,4031,2990,5827,1129,2259,6894,2088,31,3962,8143,5719,115,500,6361,1244,6389,4523,3947,8313,9233,3833,3132,4420,9002,6593,2099,1806,6665,3210,7045,1359,3970,9195,4198,6136,1424,906,6189,545,5835,8713,6339,3390,2419,7986,3368,7168,6671,8299,7523,8562,1243,6525,8116,3581,3967,8696,7465,8496,5141,7646,8139,8186,6665,4851,4526,4888,9267,297,468,7531,415,8043,9902,4527,9190,2215,9941,8398,7977,9171,9119,330,1287,7903,2214,6074,9561,6669,9789,5833,6996,788,5464,8933,6170,4599,486,8060,6553,2580,9994,633,1522,4431,4748,1826,3233,696,2882,8274,8149,6617,9704,9463,8573,2962,9029,1743,9413,1,9045,2983,7816,7027,5089,2899,6010,9476,926,2266,140,9536,9102,4866,8645,2933,5622]

if __name__ == '__main__':
    main(blocks, n)

[Vaktmester]

Prøvde meg på den første og enkleste løsningen som Nebu kalte "Standard grådighet".

Kode: Velg alt

# -*- coding: utf-8 -*-
from statistics import pstdev

def main(name, n, blocks):
    blocks.sort()
    solutions = [blocks[i::n] for i in range(n)]
    heights = list(map(sum, solutions))
    print ("Problem: ", name)
    print ("Høyder: ", heights)
    print ("Standardavvik ",  pstdev(heights))
    print()


data = [["site 1",2,[425,709,704,891,152,805,208,74,807,214,471,265,250,820,153,168,308,342,612,836,845,793,968,155,30,377,129,79,622,136,579,247,756,355,80,590,335,688,940,780,669,758,482,464,939,617,316,341,863,945,982,621,286,833,673,70,268,185,205,366,766,619,254,966,926,781,740,898,228,497,705,747,28,678,94,503,478,524,23,599,499,403,603,846,119,274,726,753,706,338,191,776,267,261,212,743,373,344,818,83,294,745,799,715,452,32,455,666,654,218,112,500,246,624,917,264,421,597,127,895,525,50,363,339,802,708,14,429,679,465,484,69,298,241,516,303,911,604,220,369,81,873,116,401,661,337,779,762,390,627,912,189,501,881,507,485,378,924,975,555,126,858,109,539,914,804,955,187,19,481,976,613,751,237,967,963,544,292,102,746,593,668,674,958,736,62,463,124,879,675,131,346,211,520,59,238,959,925,717,291,828,243,418,232,144,505,167,732,629,680,92,413,42,258,862,312,908,956,657,467,66,142,996,530,841,852,55,819,190,606,572,712,5,449,76,872,552,193,528,941,209,388,137,445,801,396,947,916,466,931,60,554,227,486,651,974,289,90,132,161,913,51,24,640,923,537,857,962,419,181,108,204,727,595,106,936,115,270,352,333,58,110,82,535,504,957,518,343,871,849,813,748,903,360,671,739,182,615,944,440,17,847,407,35,574,646,154,376,543,556,134,68,649,534,919,48,973,608,837,456,660,313,775,43,493,691,665,196,332,15,370,201,633,21,876,639,296,783,130,540,653,385,272,93,616,287,424,53,236,340,983,817,981,105,527,575,838,96,735,721,304,991,951,384,149,402,821,37,877,375,391,722,22,300,829,954,280,459,290,231,49,173,694,315,488,888,18,310,215,150,31,978,928,839,759,663,480,605,420,850,327,65,808,2,408,921,183,929,786,371,844,565,789,52,361,750,800,628,13,784,724,894,562,693,436,356,284,814,285,707,977,89,146,634,350,71,216,964,699,655,623,720,861,770,141,40,412,906,242,169,213,710,461,952,647,322,336,965,652,273,454,884,741,000,725,27,869,164,788,411,803,950,509,195,367,423,122,100,47,120,7,902,598,812,271,203,582,222,430,749,251,405,773,317,765,324,659,138,410,815,394,522,602,927,792,496,433,226,446,97,57,868,601,949,492,993,645,854,811,498,532,806,744,865,282,121,325,278,538,842,658,199,474,84,41,458,256,180,123,200,513,531,764,832,910,878,810,415,672,85,676,825,700,179,54,166,569,855,86,194,457,160,117,550,358,348,594,729,240,39,664,305,260,514,521,892,244,934,683,752,899,831,896,874,479,314,592,219,279,561,564,224,946,253,140,114,437,768,95,798,16,61,197,690,147,642,252,64,301,581,571,714,961,380,681,589,502,427,523,785,920,738,11,856,611,288,987,809,165,795,999,223,626,576,98,239,103,379,563,840,897,359,328,383,969,638,381,998,235,397,536,362,73,716,620,229,353,248,460,994,393,128,91,937,830,882,511,320,8,416,697,515,113,519,34,698,323,148,763,389,915,283,618,171,777,428,557,349,529,718,281,409,206,757,632,77,177,824,354,687,560,56,99,625,631,584,72,439,447,737,566,490,512,985,984,656,559,470,684,4,1,299,883,885,202,585,406,577,867,255,526,682,890,392,935,259,637,918,487,309,848,685,583,364,843,245,887,443,553,175,835,542,495,125,163,25,249,643,145,345,719,591,573,960,990,701,198,257,26,489,477,33,689,451,221,38,101,570,143,277,372,395,157,414,468,614,188,444,790,989,45,20,186,686,548,87,794,506,207,864,630,438,979,75,29,909,782,263,234,306,404,791,771,702,311,104,713,321,162,12,111,547,374,533,510,9,107,970,266,176,870,587,269,971,568,462,67,662,853,860,472,275,816,368,78,772,88,326,432,36,172,728,859,417,295,382,822,600,826,426,986,730,63,767,387,827,3,635,422,133,938,904,541,769,276,711,473,351,901,334,834,46,331,610,386,329,434,677,545,262,442,318,178,475,567,580,483,453,225,293,905,695,761,549,398,517,184,578,796,932,907,886,667,948,943,546,930,596,118,650,734,893,558,648,980,997,933,889,900,696,588,636,170,551,307,851,448,778,731,703,435,491,192,6,644,158,494,319,469,742,297,953,230,44,995,972,400,10,866,670,992,156,431,508,875,357,609,159,217,586,607,922,347,450,988,210,755,330,641,233,139,135,302,880,787,692,754,823,760,797,723,365,441,942,399,476,174,774,151,733]],

["site2",3,[1022,486,1003,955,582,314,742,1008,0,711,885,806,805,624,382,0,1081,229,726,644,712,941,799,921,1059,237,453,0,913,862,1021,0,621,454,476,262,714,903,0,925,805,462,1102,1092,231,929,707,378,1134,1177,1048,563,619,547,809,552,246,890,683,986,746,776,0,0,957,393,209,0,609,416,271,1125,437,793,402,863,1106,205,585,1138,657,248,641,345,232,616,715,414,680,1126,0,981,1051,919,1134,207,540,536,1113,797,428,957,614,0,815,581,855,1066,679,1107,1111,1180,835,0,219,451,254,1020,604,1099,267,247,440,298,493,0,424,1147,631,1064,204,585,740,1117,882,212,258,539,697,1054,984,670,439,925,1087,0,659,855,982,707,421,0,982,777,1107,1108,599,256,886,604,966,804,505,483,600,969,837,383,0,244,0,0,1002,304,754,866,1160,0,0,549,1161,1095,1066,470,643,0,585,906,426,469,282,623,220,1100,806,859,808,794,866,269,337,1167,1186,549,236,887,744,786,670,568,252,225,1152,408,239,784,1081,773,613,993,722,711,1182,378,512,586,345,0,373,432,424,361,606,1025,1093,940,234,781,838,444,447,1047,557,413,230,0,1061,748,1035,1024,455,302,555,230,447,380,689,940,720,953,395,914,1129,649,1021,629,0,1014,548,726,862,1152,956,854,839,801,791,336,1042,0,454,532,931,425,1024,608,1041,0,777,1147,1103,0,492,416,313,842,894,210,903,1039,413,553,760,1031,279,957,0,669,749,706,955,972,0,311,454,0,948,767,1128,527,0,757,278,1046,959,845,537,695,657,258,1128,388,1077,1169,1179,473,750,424,676,1163,1112,793,386,236,1038,1179,1138,308,423,946,652,847,960,289,555,682,476,837,910,1009,243,418,899,596,0,962,247,1179,267,215,1023,1188,968,936,527,0,1074,445,1009,0,834,346,933,450,1085,427,1066,215,234,619,536,323,1070,639,647,1118,236,363,771,0,875,418,810,1154,614,0,695,962,682,1115,469,233,1068,1027,792,855,358,628,428,407,309,262,689,839,267,0,0,607,1129,534,317,338,334,861,913,965,753,628,849,1161,982,1026,804,990,596,610,864,437,311,463,1196,1130,270,439,1036,303,638,526,234,286,1103,1116,0,767,0,210,720,1044,561,1152,0,355,620,401,891,995,0,236,987,220,790,854,0,353,240,964,776,0,527,614,222,1083,481,524,987,213,680,1014,234,531,0,360,466,0,341,871,310,0,899,384,839,953,816,776,380,736,628,464,896,924,606,448,1181,564,400,1108,1049,751,368,1034,603,0,0,840,281,453,425,676,692,507,0,409,818,1166,1068,1146,0,654,739,0,0,0,406,1197,1119,802,685,226,575,0,250,559,379,330,1120,1092,1025,1102,0,662,1167,470,1089,274,399,979,1089,512,432,345,989,1081,511,567,308,208,346,731,324,921,1200,261,1177,1141,365,1148,524,0,540,572,1041,718,716,664,339,459,784,0,704,1106,1124,747,248,312,434,824,773,762,235,1000,1065,215,579,942,1054,1179,482,1120,1138,441,862,785,747,288,872,0,792,475,1128,870,793,1143,803,1095,400,928,577,0,0,0,752,784,1165,0,387,0,0,1004,704,709,1163,738,0,815,781,984,438,1105,952,0,419,531,492,718,1143,0,322,590,835,336,609,952,1087,505,828,829,0,347,0,563,867,876,291,0,652,488,1180,450,824,1132,622,1145,324,603,0,0,625,301,586,261,725,760,777,0,621,0,932,979,269,1169,981,232,0,1169,0000,957,773,560,643,829,490,629,506,348,1090,542,507,568,0,0,1046,892,1160,817,866,732,640,1057,666,0,377,423,747,603,0,1048,616,0,1117,1183,325,781,530,381,829,1004,666,858,600,870,439,539,286,806,869,286,931,720,659,0,931,395,849,327,992,888,278,776,1011,0,811,836,250,1126,900,583,764,386,921,799,757,638,979,0,1194,528,802,727,856,257,566,640,0,722,828,217,1058,459,394,212,1173,698,909,417,654,0,956,551,1078,402,213,386,278,812,370,282,438,952,354,648,1130,974,827,591,836,648,696,0,898,0,1195,712,665,708,560,1046,1183,245,0,288,1020,405,974,1013,226,1030,563,417,433,0,917,693,348,669,361,1058,563,881,1011,620,708,307,1150,648,1153,646,1196,824,892,713,584,0,868,953,681,896,1137,735,1124,1199,1122,911,0,1020,1037,325,227,520,1177,624,966,874,835,1042,994,375,0,411,421,1148,732,934,0,0,1037,972,1036,874,937,475,530,547,308,896,0,413,1033,1159,379,1121,306,738,914,0,867,0,398,795,1018,510,942,376,915,521,401,462,217,1081,423,0,486,865,832,759,629,831,654,992,409,1146,0,371,787,720,647,905,446,817,636,1014,817,294,1196,0,701,243,571,1054,327,587,245,1046,453,509,1119,412,206,734,959,729]],

["site3",23,[2008,7533,650,9022,1634,9978,5565,8519,9269,5193,5484,2434,3008,5286,1744,8837,3531,6080,3147,4929,6319,3396,1914,6680,4015,8774,6882,3909,63,4580,6662,6442,1094,5254,1773,1389,5605,2623,6549,5840,2192,1704,7923,576,2403,8289,297,5323,8406,7344,4052,4081,4448,5082,5492,9677,8447,5309,8972,1452,9937,9467,2441,4190,2845,1166,3477,2288,5487,3929,2614,9896,4959,4191,8859,4332,3300,5693,3447,4439,4711,2956,533,9099,1688,4059,450,780,5554,9934,799,9711,6131,8500,4259,5421,9777,9246,2915,5308,7408,7385,3415,234,6257,2602,8627,2933,6838,1287,3368,1777,1765,4458,4079,4031,3452,441,2939,9324,7802,7636,5152,2387,673,2900,5734,7064,8788,9487,7380,5767,7423,7510,8505,9450,6215,8406,7545,6081,6161,1405,999,3265,2480,6237,3331,1515,441,897,708,5873,808,1130,6204,8985,1729,3906,4351,7084,9413,3656,62,7618,7622,7284,1326,5585,6435,4865,9393,7600,6353,5001,4289,7771,8076,2653,3949,2920,9252,4158,6278,3303,306,5184,1068,2275,6328,7553,7818,1349,6552,4116,4039,4961,909,417,7066,8721,292,4737,4147,8960,1408,5305,1876,544,6100,9640,9857,4056,7167,1,9861,7979,3560,6224,7241,3230,691,7629,46,7104,1293,5012,7942,3446,264,7988,6076,7986,9779,7931,4245,2180,8703,7695,9396,9555,5730,4334,2526,8203,4828,6065,125,4823,3631,2516,3916,4101,1036,3326,8992,5252,2192,8050,6975,441,9265,8201,4129,3011,309,7236,5859,7303,9850,5348,5443,8527,7556,3602,3335,5937,9811,201,4004,4632,5122,9174,1,9715,7906,7955,2200,4105,4429,2197,8922,7073,506,1,136,8106,8952,7814,2513,5293,9968,6564,9632,1229,9969,4399,5507,45,4804,5216,3469,3121,2502,7199,7972,5594,8853,4600,9922,7508,3714,6430,2140,4421,2219,2626,7498,6984,6300,3780,1602,284,1,4984,1414,1710,1528,9901,1433,4229,7014,8913,6262,6967,980,1611,4688,8702,6955,6225,1697,8402,3610,6811,4322,9741,9284,1456,895,4409,5169,4783,377,1647,8663,7932,3220,812,1656,4573,5545,3866,5853,5764,4248,1776,1,2997,7981,5922,9363,9035,9182,1019,1519,8341,2931,457,7807,7360,2238,4145,7184,7406,1,4810,3171,1239,2527,1029,3,6467,2638,1,-3,2576,3679,5579,7112,4011,6038,4984,2498,1935,3359,5472,8129,5276,810,8714,3212,1,5011,7069,3189,8950,1123,1,500,4133,9106,4190,5263,513,1342,7507,9140,4539,8555,4181,1441,2748,7426,7153,8535,6782,2562,4681,990,1510,1250,9618,6440,2654,841,3841,7336,7462,5938,4363,1,657,6177,4344,3597,455,745,7948,4291,1557,1092,3055,3630,9196,8799,1207,8276,9654,1801,9628,5297,1173,594,6119,8720,9992,4071,7424,6148,5418,9202,6654,246,2628,7317,2668,6111,1988,2623,8271,6871,2412,746,3636,3597,9797,1166,907,4838,1885,3667,9621,4487,9171,8382,8942,1366,1594,4587,6457,4821,9540,8334,9504,3839,9969,5196,4390,6613,1,6205,9231,2384,5193,582,7713,3086,4252,9587,4052,-5,1158,8423,4662,1370,5808,4886,6607,1625,2968,5725,8776,5434,873,4649,185,2916,4375,6528,9547,9872,5192,5626,9827,4889,4910,6252,9733,5987,2943,5622,5542,1084,9064,1,274,553,2516,3499,4738,4965,7661,9032,756,9281,9396,426,5116,6227,597,2614,3277,2042,7742,2901,9041,8866,6239,8588,8727,4250,670,4657,3881,4583,4043,9346,2708,5419,1188,945,3165,1444,8868,3318,9335,5353,3107,8557,9344,5465,558,5649,1010,3923,1,7247,7739,7474,2400,9919,8629,8945,4510,5098,6846,4411,2008,4200,4994,1281,6842,6446,2701,5286,791,7538,7738,3926,2864,4638,7776,2129,8957,1379,1,2215,9309,4065,9383,6538,1,4203,5441,8399,1196,8287,6283,8347,2305,5293,5105,8817,4888,196,6699,3710,9332,7559,2191,5888,8813,7113,7504,7355,2463,4107,4969,5988,3870,4015,3904,806,8534,3178,5980,8673,3079,1013,4036,7902,2051,247,8435,9124,6833,1890,6399,6963,2686,1233,9072,1624,3023,8102,2779,8664,5105,2266,5110,5048,2883,2299,3895,860,3995,6309,2951,523,1042,2314,3168,2088,4225,6161,3719,1054,5601,9037,4317,9156,1712,7504,953,1087,2589,9696,2240,4506,5977,5073,3002,3613,6006,963,8137,5783,3685,9489,8032,3607,4545,5963,6545,7828,2687,4396,4915,4442,4752,4329,1537,3111,6173,2820,6967,4630,1390,8669,1593,9602,988,8787,3291,8574,4521,5007,2947,190,7863,3269,7335,7052,4494,740,1,8406,3958,2369,2824,8327,4934,6623,2099,7076,1882,7097,657,593,585,7985,2426,9623,6404,7284,539,3602,1304,710,2217,558,2093,3085,6273,9821,8836,6681,5988,7839,3260,9268,2762,3907,6605,1,2870,3358,762,210,2028,9269,6206,4821,7223,3986,1471,1872,9575,464,3678,8220,4784,6028,8366,6302,4097,9266,6713,7431,9583,2957,7918,4031,2990,5827,1129,2259,6894,2088,31,3962,8143,5719,115,500,6361,1244,6389,4523,3947,8313,9233,3833,3132,4420,9002,6593,2099,1806,6665,3210,7045,1359,3970,9195,4198,6136,1424,906,6189,545,5835,8713,6339,3390,2419,7986,3368,7168,6671,8299,7523,8562,1243,6525,8116,3581,3967,8696,7465,8496,5141,7646,8139,8186,6665,4851,4526,4888,9267,297,468,7531,415,8043,9902,4527,9190,2215,9941,8398,7977,9171,9119,330,1287,7903,2214,6074,9561,6669,9789,5833,6996,788,5464,8933,6170,4599,486,8060,6553,2580,9994,633,1522,4431,4748,1826,3233,696,2882,8274,8149,6617,9704,9463,8573,2962,9029,1743,9413,1,9045,2983,7816,7027,5089,2899,6010,9476,926,2266,140,9536,9102,4866,8645,2933,5622]]]


if __name__ == '__main__':
    for p in data:
        main(p[0],p[1],p[2])

Output:

Kode: Velg alt

Problem:  site 1
Høyder:  [249500, 250000]
Standardavvik  250

Problem:  site2
Høyder:  [212465, 211583, 212141]
Standardavvik  364

Problem:  site3
Høyder:  [213846, 214320, 214760, 215217, 215602, 216049, 216481, 216964, 217447, 218005, 218442, 208973, 209418, 209880, 210367, 210747, 211194, 211454, 211817, 212213, 212511, 213008, 213384]
Standardavvik  2799

.. et stykke igjen til en perfekt løsning, mao...

:-)

[Nebuchadnezzar]

Husk at du må sortere brikkene fra størst til minst. Da funker ikke blocks.sort, du trenger

Kode: Velg alt

bricks.sort(reverse=True)

For å oppnå null på den første er det bare å sortere listen, også snu halvparten.

1 2 3 4 5 6 blir for eksempel

1 2 3
6 5 4

Mens de andre er litt mer tricky ja. Fordelen med grådighet er at den har $O(n)$ kjøretid.
Har du høyere enn det tar ting fryktelig lang tid.

[Nebuchadnezzar]

Klarte å skrive en mye bedre kode

http://pastebin.com/A8sVnGxD

Løsningen min ble at jeg "fant" en ekstremt rask og presis algoritme
som deler listen i to. Ikke nødvendigvis helt like, men ganske presist.

Dersom jeg skal dele listen i to bruker jeg Karp-algoritmen. Derimot
om jeg skal gjøre en annen inndeling kjører jeg først grådighet.

Da har jeg ett utkast som jeg kan forbedre ved algoritmen ovenfor.
Jeg finner det største og minste tårnet i grådighet og kjører de to
tårnene gjennom Karp. Dette gjør jeg X antall ganger.

Kommer nok til å legge inn at den skal bryte om den finner en optimal
løsning og litt sånt, men foreløpig virker algoritmen fantastisk.

På de tre vektorene får jeg henholdsvis

$ \hspace{1cm}
[T_2=0, T_3=0.471, T_{23} = 1.931]
$

Som er en latterlig forbedring fra tidligere =)