In this programming problem you'll code up the dynamic programming algorithm for computing a maximum-weight independent set of a path graph.
The file mwis.txt describes the weights of the vertices in a path graph (with the weights listed in the order in which vertices appear in the path). It has the following format:
[number_of_vertices]
[weight of first vertex]
[weight of second vertex]
...
For example, the third line of the file is "6395702," indicating that the weight of the second vertex of the graph is 6395702.
Your task in this problem is to run the dynamic programming algorithm (and the reconstruction procedure) from lecture on this data set. The question is: of the vertices 1, 2, 3, 4, 17, 117, 517, and 997, which ones belong to the maximum-weight independent set? (By "vertex 1" we mean the first vertex of the graph---there is no vertex 0.) In the box below, enter a 8-bit string, where the ith bit should be 1 if the ith of these 8 vertices is in the maximum-weight independent set, and 0 otherwise. For example, if you think that the vertices 1, 4, 17, and 517 are in the maximum-weight independent set and the other four vertices are not, then you should enter the string 10011010 in the box below.
In [22]:
FILE = "mwis.txt"
# FILE = "test2.txt"
fp = open(FILE, 'r')
data = fp.readlines()
n= int(data[0])
weights = data[1:]
A = [int(weights[i]) for i in range(n)]
In [23]:
# The DP algorithm
for i in range(2,n):
A[i] = max(A[i-1], A[i-2]+int(weights[i]))
In [24]:
print (A)
[4962786, 6395702, 10564376, 10564376, 17349002, 17349002, 20231727, 26659664, 26659664, 36479518, 36479518, 37949581, 40679214, 42572717, 48840116, 48840116, 52729273, 57051330, 59290257, 65886746, 65886746, 69173439, 69173439, 73036229, 73036229, 82803693, 82803693, 84937086, 84937086, 89474452, 91592695, 95025575, 100632244, 100632244, 100936945, 106400893, 106400893, 114822564, 114822564, 121615011, 121615011, 126307742, 126307742, 135652450, 135652450, 139997660, 145397149, 149404882, 151877551, 157390012, 157390012, 161430970, 165350863, 166825486, 169375789, 173609558, 173609558, 180496499, 181105113, 186150585, 186150585, 195043269, 195043269, 196583061, 196871967, 201324417, 201324417, 201651757, 208958637, 208958637, 214059863, 215917381, 215917381, 223149245, 223364621, 223927887, 226485044, 226485044, 232935512, 232935512, 240210540, 240210540, 247365437, 247365437, 256805839, 256805839, 259491984, 261905354, 263268041, 267671298, 272203066, 274148306, 275693956, 275839870, 277919128, 284350289, 287707650, 293834439, 294944398, 301168789, 301168789, 301611862, 305008773, 305008773, 310947721, 313551168, 313551168, 313858240, 316619372, 323766779, 323766779, 332725273, 332725273, 333214436, 335633427, 338714539, 343096658, 343096658, 343897769, 344408684, 347280865, 354086567, 354253183, 363898790, 363898790, 365675981, 371096778, 373831512, 373831512, 374088324, 378150582, 383723465, 387733737, 387733737, 387883641, 397456692, 397456692, 403455431, 404534323, 406361111, 412582066, 412582066, 417910015, 420844094, 424356672, 427789909, 429557760, 429608799, 433013155, 433013155, 434400971, 434400971, 439963539, 439963539, 447375159, 447375159, 450901762, 450901762, 456783423, 460647951, 460647951, 461788711, 461788711, 470759973, 470759973, 476938336, 477253043, 482246241, 482246241, 491676824, 491676824, 494268011, 496438929, 496438929, 504414203, 504414203, 508161798, 508161798, 513695777, 513695777, 520022758, 520226345, 526514493, 526514493, 532170864, 534783115, 537068720, 537068720, 538738594, 544811766, 544811766, 546515159, 550908119, 550908119, 554973137, 556916984, 558635177, 558635177, 564955489, 568158667, 571538989, 571538989, 578441897, 580257912, 583395735, 584750084, 584802645, 592203831, 594054465, 594054465, 603835739, 603835739, 605231686, 609140001, 609140001, 618236012, 618236012, 625213125, 625213125, 633211544, 634326389, 634326389, 640275325, 640275325, 646727969, 647667959, 651047855, 656793426, 656793426, 664336906, 664336906, 668436353, 669229858, 676033374, 677591658, 682347434, 682347434, 685472742, 685540284, 694625355, 694625355, 697918332, 704186134, 707407163, 713195477, 713195477, 714206329, 714740733, 722830122, 722830122, 725778909, 726639252, 728452305, 728700104, 731106023, 732876300, 732876300, 741337867, 741337867, 742544821, 748558074, 751716423, 751896639, 754777807, 761570690, 761570690, 761952699, 761952699, 767955135, 767955135, 777943190, 777943190, 786879512, 786879512, 787285434, 787878423, 796667674, 796667674, 805889101, 805889101, 807661614, 808705359, 815920012, 815920012, 816240877, 822620903, 824936113, 824936113, 834196678, 834196678, 838088570, 841763819, 841763819, 848956151, 848956151, 858088959, 858164669, 860185285, 860185285, 868535027, 868535027, 872740038, 872740038, 872811261, 877612062, 877723719, 880461113, 882505523, 886722675, 889796038, 891730348, 897254472, 897254472, 905805277, 905805277, 908618738, 908618738, 916276575, 916276575, 921068604, 923814750, 926199705, 932820818, 932820818, 942137853, 942137853, 950369358, 951625336, 953714456, 953714456, 954168439, 959304021, 961460545, 962007387, 966759426, 966759426, 968015663, 968981536, 970700183, 976683142, 978553982, 978553982, 986405650, 986405650, 989336023, 989336023, 993631975, 993631975, 1001022213, 1001022213, 1009393988, 1009393988, 1015600400, 1015600400, 1022413246, 1022413246, 1024205151, 1024205151, 1031435415, 1031435415, 1038722350, 1038722350, 1038791401, 1039485157, 1047302327, 1047302327, 1057285366, 1057285366, 1064062390, 1064062390, 1066952970, 1066952970, 1076147689, 1076147689, 1083674346, 1083674346, 1091641756, 1092460661, 1095701620, 1098842898, 1102774772, 1106388591, 1109206001, 1109206001, 1114995974, 1117319572, 1122560257, 1123137285, 1129392534, 1129392534, 1131657742, 1131657742, 1133414821, 1133414821, 1141909925, 1141909925, 1149330776, 1149330776, 1156600907, 1156600907, 1158075944, 1165724837, 1167104103, 1170715286, 1170715286, 1180412142, 1180412142, 1188709260, 1188709260, 1194148039, 1194148039, 1194988833, 1198312113, 1203016516, 1208234223, 1208234223, 1214261118, 1214261118, 1215189457, 1218879888, 1223180074, 1225244016, 1225244016, 1227276592, 1229522998, 1233376857, 1236439989, 1236762133, 1238060440, 1241700479, 1244303188, 1244504742, 1251768010, 1251768010, 1256803935, 1256803935, 1258796791, 1265520020, 1267832935, 1267832935, 1276286596, 1276286596, 1282084138, 1282084138, 1283034294, 1287970898, 1291188197, 1293077728, 1300515337, 1300515337, 1305537381, 1305537381, 1306504066, 1310709730, 1310709730, 1310823865, 1310824361, 1311774660, 1316351304, 1319992663, 1320843298, 1327822137, 1327822137, 1333138494, 1333138494, 1342812281, 1342812281, 1345335691, 1345335691, 1350029489, 1355275847, 1356972010, 1359458168, 1362355022, 1364318449, 1370725942, 1371891880, 1378494113, 1378494113, 1378630219, 1382052349, 1382052349, 1385591659, 1385591659, 1390654467, 1390654467, 1392399827, 1397774107, 1397774107, 1397835765, 1400898645, 1405009671, 1405009671, 1412987810, 1412987810, 1419978511, 1422136532, 1426990351, 1426990351, 1435518538, 1435518538, 1438205354, 1441399017, 1442944008, 1450178843, 1450178843, 1452611002, 1456906290, 1460423235, 1463572270, 1469264095, 1472084634, 1472953495, 1479440054, 1479440054, 1485245207, 1485346473, 1488243433, 1494753459, 1494753459, 1502296776, 1502296776, 1505643527, 1505643527, 1514159960, 1514159960, 1521025539, 1521916294, 1530477051, 1531098952, 1538905497, 1538905497, 1543492080, 1546831486, 1546831486, 1547844360, 1556710822, 1556710822, 1565201118, 1565201118, 1567262100, 1573664759, 1574326492, 1577160173, 1581107779, 1581107779, 1584519455, 1589280597, 1593103441, 1598579750, 1598579750, 1600687445, 1603150551, 1606387436, 1611425051, 1614046766, 1615358454, 1619135471, 1619135471, 1621454003, 1621454003, 1626479030, 1629093125, 1629093125, 1629885862, 1634552307, 1634552307, 1636723197, 1644341773, 1644341773, 1652252834, 1652252834, 1660381326, 1660381326, 1669076811, 1670040752, 1672346099, 1672526055, 1680263828, 1680756813, 1688502998, 1688502998, 1694650335, 1697307364, 1697307364, 1700166595, 1703005164, 1706083485, 1706083485, 1707378901, 1712084532, 1716444636, 1716444636, 1722479582, 1722479582, 1730010220, 1730010220, 1734237866, 1738027238, 1743409991, 1743499831, 1752117384, 1752117384, 1756305761, 1756305761, 1761678492, 1761678492, 1767460032, 1767460032, 1774404939, 1774404939, 1777609650, 1784056997, 1784056997, 1792615642, 1792615642, 1798377986, 1799507523, 1799718262, 1804079786, 1809048711, 1809048711, 1818335336, 1818335336, 1821822480, 1821822480, 1825509165, 1829926326, 1829926326, 1838895374, 1838895374, 1840655200, 1841555383, 1847131639, 1847131639, 1849034557, 1853672793, 1853672793, 1863512348, 1863512348, 1870963619, 1870963619, 1872764523, 1874449750, 1880725785, 1880725785, 1886348576, 1886348576, 1892440067, 1892440067, 1897447294, 1902206887, 1904937025, 1910411421, 1910411421, 1920127511, 1920127511, 1929535133, 1929535133, 1931582605, 1931589433, 1933986941, 1940386676, 1942866950, 1942866950, 1949476558, 1949476558, 1951288041, 1959252288, 1959252288, 1968406618, 1968406618, 1970755755, 1970755755, 1971133139, 1979020769, 1979020769, 1980289325, 1983014305, 1983014305, 1985992653, 1989881280, 1993184883, 1998978484, 1998978484, 2007368307, 2007368307, 2010575371, 2010596308, 2019635779, 2019635779, 2024192666, 2024192666, 2024762357, 2033062827, 2033511023, 2038383434, 2038383434, 2045130213, 2045130213, 2046228218, 2048331428, 2049906870, 2055318724, 2055318724, 2064410652, 2064410652, 2072261916, 2073090066, 2077335256, 2077335256, 2080884976, 2083827534, 2088232873, 2091978451, 2097305788, 2101880041, 2101880041, 2106807129, 2106807129, 2107545952, 2113334738, 2116034718, 2116034718, 2117771023, 2121621736, 2121621736, 2127940994, 2130948121, 2137666086, 2137666086, 2139418068, 2146079874, 2146079874, 2153011388, 2154114481, 2160724351, 2160724351, 2166328511, 2166328511, 2174908888, 2174908888, 2181902922, 2181902922, 2190926490, 2190926490, 2194089081, 2195788648, 2199595722, 2203887185, 2203887185, 2209311131, 2209311131, 2211317969, 2215261662, 2218202392, 2221157488, 2221157488, 2228453868, 2229684648, 2229684648, 2230614516, 2236412263, 2236412263, 2238251915, 2246295505, 2246295505, 2255647460, 2255647460, 2264526291, 2264526291, 2265642608, 2267384028, 2272391531, 2272391531, 2281462520, 2281462520, 2289958356, 2289958356, 2291250068, 2293906860, 2293906860, 2295188739, 2297359294, 2297359294, 2297414449, 2297428960, 2307160976, 2307160976, 2315377467, 2315377467, 2316219319, 2321444942, 2321444942, 2326257059, 2330951259, 2330978238, 2334381552, 2339074942, 2339074942, 2347155809, 2347155809, 2354142000, 2354142000, 2355660225, 2363286943, 2363286943, 2363955678, 2370353767, 2370353767, 2377251448, 2379960186, 2379960186, 2384733282, 2384733282, 2389900198, 2389900198, 2393657430, 2396303459, 2396303459, 2404722420, 2404722420, 2409041601, 2409041601, 2416108072, 2416108072, 2426078583, 2426078583, 2435797297, 2435797297, 2437595697, 2444374661, 2444374661, 2452136173, 2452136173, 2453434802, 2461887350, 2461887350, 2466688267, 2467935747, 2470569868, 2473348892, 2479913864, 2479913864, 2480482399, 2488353019, 2488353019, 2489129415, 2497148155, 2498243819, 2503323656, 2507323648, 2510096777, 2515495750, 2519977229, 2519977229, 2522132905, 2522159733, 2527712456, 2529816538, 2537573570, 2537573570, 2546360409, 2547191210, 2551637504, 2555646976, 2557374635, 2563692568, 2563692568, 2569338712, 2570291518, 2577034599, 2579679190, 2579679190, 2580636431, 2587038658, 2587038658, 2595659258, 2595659258, 2599958029, 2603660204, 2609925333, 2612830466, 2613978087, 2616413962, 2620073643, 2620227690, 2628098885, 2628098885, 2634163028, 2634163028, 2641490993, 2641490993, 2645081112, 2645081112, 2654846950, 2654846950, 2661875825, 2661875825, 2665620044, 2665620044, 2667828838, 2670139781, 2670730214, 2675291355, 2675291355, 2683112334, 2683112334, 2688423050, 2688423050, 2694506846, 2694506846, 2702392055, 2702392055, 2706280150, 2706280150, 2709490637, 2709789458, 2715175865, 2715175865, 2717143538, 2717143538, 2720010273, 2727004053, 2727004053, 2730881236, 2733106401, 2733679513, 2738805939, 2738805939, 2740434267, 2743838940, 2744480685, 2749020155, 2752592338, 2756505969, 2758077967, 2762523863, 2762523863, 2767247175, 2767803626, 2771795294, 2771795294, 2774367135, 2774367135, 2784301511, 2784301511, 2786985342, 2787056641, 2792457505, 2792457505, 2799097291, 2800762321, 2803834133, 2803834133, 2811864043, 2811864043, 2818005331, 2818005331, 2819263571, 2819263571, 2825413686, 2825413686, 2833197139, 2834760264, 2842782793, 2842782793, 2845270590, 2851447647, 2851447647, 2860196624, 2860196624, 2862470404, 2868288827, 2870891182, 2876271006, 2879388150, 2879468935, 2885818067, 2885818067, 2891121733, 2891121733, 2899642620, 2899642620, 2903930589, 2909272641, 2913921317, 2917728124, 2919354633, 2922501159, 2927787609, 2927787609, 2930219257, 2936024870, 2939848077, 2939848077, 2947394128, 2948442421, 2950698717, 2955353732]
In [25]:
# The Reconstruction Algorithm
def reconstruct(A, weights):
S = []
i = len(A)-1
while (i>=0):
if (A[i-1]>= A[i-2]+ int(weights[i])):
i -=1
else:
S.append(i)
i -=2
return S
S = reconstruct(A, weights)
In [26]:
print (S)
sum_ = 0
for n in S:
sum_ += int(weights[n])
print (sum_)
[999, 997, 994, 992, 990, 988, 986, 984, 982, 980, 978, 976, 974, 972, 970, 968, 965, 963, 961, 959, 957, 955, 953, 951, 949, 947, 945, 943, 941, 939, 937, 935, 933, 931, 928, 926, 923, 920, 918, 916, 914, 912, 910, 908, 906, 904, 902, 899, 897, 895, 893, 891, 889, 887, 885, 883, 881, 879, 877, 875, 872, 870, 867, 865, 863, 860, 858, 856, 854, 852, 850, 848, 845, 842, 840, 838, 836, 833, 831, 828, 826, 824, 822, 820, 818, 815, 813, 811, 808, 805, 802, 800, 798, 796, 794, 792, 789, 787, 785, 783, 780, 777, 775, 773, 771, 769, 767, 765, 762, 759, 756, 754, 751, 749, 747, 744, 742, 740, 738, 736, 734, 732, 729, 727, 725, 722, 720, 718, 716, 714, 712, 709, 707, 705, 703, 701, 698, 696, 694, 691, 689, 687, 685, 683, 681, 678, 675, 672, 670, 668, 665, 663, 661, 659, 657, 655, 653, 651, 648, 646, 644, 642, 640, 638, 636, 633, 631, 629, 627, 624, 622, 620, 618, 616, 614, 612, 609, 607, 605, 603, 601, 599, 597, 595, 593, 591, 589, 587, 585, 583, 580, 578, 576, 574, 572, 570, 568, 565, 562, 559, 557, 555, 553, 551, 549, 547, 544, 542, 540, 538, 536, 533, 530, 528, 526, 524, 522, 520, 518, 516, 513, 511, 509, 507, 504, 502, 499, 497, 495, 493, 491, 489, 487, 484, 482, 480, 477, 475, 473, 471, 469, 467, 465, 463, 461, 459, 457, 455, 453, 450, 448, 446, 444, 442, 440, 438, 436, 434, 432, 430, 428, 426, 424, 421, 419, 416, 414, 412, 409, 407, 405, 403, 401, 398, 396, 394, 392, 390, 388, 386, 384, 382, 380, 378, 376, 374, 372, 370, 368, 366, 364, 362, 360, 358, 356, 354, 352, 350, 348, 346, 344, 342, 340, 338, 336, 334, 332, 330, 328, 326, 324, 322, 320, 317, 315, 313, 311, 309, 307, 305, 303, 301, 299, 297, 295, 293, 291, 288, 286, 284, 282, 280, 278, 276, 274, 272, 270, 268, 266, 264, 262, 260, 257, 255, 253, 251, 248, 246, 244, 242, 239, 237, 235, 233, 231, 229, 227, 225, 222, 220, 217, 215, 213, 210, 208, 206, 204, 202, 200, 198, 196, 194, 192, 189, 186, 184, 182, 180, 178, 176, 174, 172, 169, 167, 165, 163, 161, 159, 156, 154, 152, 150, 148, 146, 144, 142, 140, 138, 135, 132, 130, 127, 125, 123, 121, 119, 116, 114, 111, 109, 107, 105, 102, 99, 97, 95, 93, 91, 89, 87, 84, 82, 80, 78, 76, 74, 71, 68, 65, 63, 61, 59, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 32, 30, 27, 25, 23, 21, 19, 17, 14, 12, 9, 7, 4, 2, 0]
2955353732
In [27]:
sol = ""
def is_in(S, v):
if v in S:
return "1"
else:
return "0"
nodes = [1, 2, 3, 4, 17, 117, 517, 997]
# nodes = [2, 4, 6 ,8, 10]
for n in nodes:
sol += is_in(S, n-1)
print (sol)
10100110
In [ ]:
Content source: jazracherif/algorithms
Similar notebooks: