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