lab6: Knapsack problem algorithms

.Random.seed <-
c(403L, 10L, 128282678L, 2142807136L, 1694599843L, 1342561729L, 
62847408L, 1396254926L, -341600711L, 757893195L, -2065458694L, 
-126692100L, -731498177L, -679799275L, 584394028L, 2110998018L, 
1171242205L, -593885225L, 1915654846L, 2048369912L, 764738267L, 
-612499143L, 1178256520L, -796318666L, -336052111L, -525397341L, 
29304818L, -458224828L, 310723591L, 1315201501L, -1968881964L, 
-42376710L, 583847237L, 1035172255L, 1854794534L, -876080208L, 
-249372589L, 2133121905L, 578505376L, 925474366L, 170939721L, 
-1195471877L, -1880297526L, -1375895252L, 1556520239L, -93568027L, 
1511783068L, 1268055794L, 545345389L, -53237593L, -10376498L, 
-1772439512L, 40707115L, -682588599L, 1940205400L, -99218938L, 
-43011103L, 1766035827L, 1504928226L, 1990989140L, 1769040983L, 
1255231565L, -1751460892L, 748294602L, 1520146485L, 325383823L, 
40527766L, 1437682496L, -1673681405L, 1899961377L, -709882096L, 
-1229495058L, 1173662873L, 544663851L, 1728708634L, 1120680668L, 
364784351L, -1788447563L, 1911595596L, -153006430L, 1590171133L, 
1091190519L, -727009250L, 737295064L, -771887557L, -1060684839L, 
-1653347992L, 125321366L, 1787993617L, 823646147L, -1303360558L, 
1535088228L, -502626905L, -1117611267L, -482705676L, -271631910L, 
-1961517787L, -125055937L, 783915974L, 2134054992L, -1935534989L, 
1799403665L, -1057011520L, -319331682L, 1558396521L, 2143022747L, 
-1549712470L, 1346103244L, 2058599055L, -1536290107L, -1362904452L, 
-1277028654L, -870555059L, 479276807L, 1776169710L, -527431736L, 
661457099L, -1135683287L, -1417051784L, 997459622L, 907104449L, 
-695158445L, 707798530L, -254419148L, 263261367L, 353066157L, 
748702148L, -1899681302L, -2146691499L, 1763952623L, -777873418L, 
703893792L, 1189633763L, 1871153025L, 1829388784L, -1828142962L, 
-1427314695L, 1307426187L, -105715270L, -1736496964L, 1311116287L, 
-1823409835L, -674643348L, 1574643394L, -1622658787L, -613087337L, 
-1760869634L, -1446192968L, -201211237L, -488353543L, 1133523528L, 
952245622L, 229412017L, 1268703459L, -2043920462L, -2020933628L, 
-1107512505L, -1446352355L, -833814380L, 469364794L, -1009831291L, 
984740703L, 1539640294L, 1983514224L, -1765578349L, 1993330225L, 
-351542048L, 363746686L, 2093533193L, -83875781L, -1614514678L, 
-1709464084L, 364571247L, 1387832741L, -845081252L, -676984526L, 
2021611565L, -1613121817L, -586933234L, 2101708264L, -1788186645L, 
528044169L, -582007784L, 1858999110L, -1159753311L, 1931526195L, 
-647819870L, -1587005292L, -1273139433L, -2116826867L, -330211292L, 
-961765366L, 1381975413L, -557366065L, 1503356886L, -675567744L, 
-985957437L, 1141845345L, -1754401840L, -820919506L, 903290585L, 
191491307L, -260182694L, 1078722332L, 1257355807L, 1616104053L, 
-722893044L, -1978688798L, 218816445L, 589522999L, -2081987874L, 
2126577176L, -1535639173L, -965240551L, 2113906088L, -1033107114L, 
193403345L, 1356306819L, 725518354L, -1842295900L, 288938855L, 
-49676099L, 952571956L, -1233609830L, -935782427L, -1517567105L, 
30999302L, -311382896L, -1524179661L, -1236258784L, 1457858748L, 
-790248880L, 713860066L, -2095939480L, 587789388L, 235473148L, 
360467442L, 1807550720L, -87166604L, 1089371144L, -976146502L, 
-349142576L, 1372662764L, -676195948L, -1606037038L, -1744338592L, 
1882177356L, -795469536L, -1361055870L, -2051744024L, -1345793812L, 
82498620L, -336450702L, -674202000L, -1562569692L, -992736456L, 
1385475226L, 1730835152L, -1998503748L, -1106424172L, 1903650434L, 
-1170523968L, -999230660L, 1926544528L, 52026914L, -1610186744L, 
1508588812L, -1537155940L, -47497710L, 1609359232L, -2028892652L, 
-288871896L, -1333885638L, -820848176L, 247583852L, -1150101196L, 
-1236629870L, 1415490400L, -363338932L, -991963168L, -1208694878L, 
-1772017752L, -1217434228L, 2019879100L, 618146162L, -2035239696L, 
666198084L, -1055043240L, 1012463162L, 1589066608L, 120920124L, 
-349085932L, 1364489666L, -1582048544L, 1366443900L, 1094635216L, 
1589524642L, 1904172072L, -1254316788L, -312956996L, 973482290L, 
-1742296640L, 1006561844L, -1081898040L, -1874290502L, -1670981232L, 
-929402388L, -1913257388L, 447848594L, 386924320L, 20269516L, 
1565947360L, -2028333374L, 821634088L, 755462828L, -600308548L, 
979474930L, 381608240L, 27931812L, 1108682424L, -899773094L, 
1707845008L, -1625263236L, 1930565908L, -1958726846L, -1570710784L, 
760944572L, 1134894928L, 409035554L, 470809928L, -1982965236L, 
-358074276L, 1070992594L, 1953307136L, 1824820564L, -667870744L, 
-1608205318L, 1416343760L, -1740456660L, 293040884L, 801245586L, 
-906562464L, -1144888052L, -1935363360L, -1051301534L, 746769064L, 
1284198988L, -861339268L, -1477950158L, -1943236496L, -19368124L, 
-1940640296L, 660569210L, -2042048976L, -1438528836L, 944754516L, 
243356738L, 1526148512L, 291994300L, -1561953840L, 611102050L, 
-748474392L, -1283471412L, 1645575932L, 183804402L, 1924966528L, 
-1547504396L, -1062226296L, -18806982L, 1361187664L, 1797936748L, 
1962840212L, -2128690862L, 640212704L, -514395444L, 252088480L, 
-624518270L, -1724534040L, 1432867564L, -1672991684L, 967910002L, 
1083548784L, -1935243740L, 764412984L, -925390822L, 519047888L, 
543302716L, 1666487444L, 1399966850L, -1329338432L, 1527290172L, 
757576336L, 308730914L, 1902257160L, 39811212L, -56005604L, -117553518L, 
1271592064L, -356417516L, -1809341144L, 520638010L, 1256940752L, 
-1220574100L, -705293644L, -3618798L, 342276064L, 516902860L, 
1089039840L, 163458594L, 429779240L, 2010165516L, 769168956L, 
889610482L, 1135753968L, -1983315132L, 434350680L, -482921926L, 
2014062320L, -942883652L, -747254252L, -755613502L, -2079182752L, 
-880046724L, 1938750672L, 1244183586L, 657980072L, -1958580340L, 
-809969220L, 432026674L, 1135343424L, 227260596L, -574758072L, 
1992342202L, 209448720L, -188049172L, -1830210476L, 2054366994L, 
848728992L, 1842397132L, 1681967968L, -626700094L, -166603224L, 
-595999316L, -1386709188L, 993922930L, -1348525264L, -1595669980L, 
-1005539272L, -1040200486L, -1185726064L, -1601886468L, 1476755348L, 
-2104810686L, -8250880L, -1979178436L, 895129168L, -916285357L, 
-646175884L, -1532018430L, -668188265L, -675947679L, -1632886874L, 
2010466724L, -1971507115L, 186156287L, 956492184L, 1030861494L, 
435137347L, -905660795L, -64144606L, -1549500400L, 364338105L, 
-334025621L, -569888932L, -425634166L, 1054290559L, -1380942903L, 
469469278L, 1759443724L, 161850077L, -1924379673L, 1219702800L, 
-143344338L, -1130696229L, 1058121405L, 402019370L, -654670648L, 
-1133485583L, -290623645L, 721565540L, 2119503506L, -772355225L, 
-1853590223L, -2123837834L, -1225076844L, 1866673061L, 903847087L, 
1992036712L, -1315055290L, 1105768691L, -673452459L, -1615769038L, 
-486842368L, 1168557289L, 940802907L, 2119198124L, -168755782L, 
1555630959L, -1822233351L, 1858744718L, 894403676L, -1862461747L, 
-1953201609L, -1389156160L, -446146658L, -863749013L, 492493805L, 
-2068021670L, -1012367080L, -103436671L, -1330822093L, -367914412L, 
110884450L, -61343497L, 1740110657L, 2057531846L, -2042815740L, 
-993268043L, -810665569L, -1158072840L, -1013908522L, 18900579L, 
-1149397467L, 305317314L, -1046234448L, -262819111L, 744211531L, 
-1663108420L, 1778329834L, 2087822623L, 1670000041L, -1072370882L, 
-669088212L, -378604419L, 493301447L, -1001351248L, 1320389070L, 
1418674939L, 837329245L, 708739722L, 56152232L, 1402377233L, 
-1074289405L, -706041852L, 1975781426L, -801611641L, 1678478545L, 
1445615190L, -1492974028L, -2073363131L, 110915471L, -1238476024L, 
-1707778778L, 1620805075L, 761122613L, 339871378L, 437379680L, 
-775425079L, -184085765L, 533486796L, -252357286L, 105633871L, 
89953561L, -467894482L, -113741508L, 1183504045L, -131755689L, 
112926880L, -382362114L, -351915829L, -22049075L, 1664195066L, 
1337541176L, -192913439L, 1379653779L, -509003084L, -1652082750L, 
-1030720553L, -576619487L, 701512678L, 1522788068L, -1839918571L, 
1577409087L, 1311789528L, -1241790474L, 134868995L, 1392827205L, 
-881938590L, 1062654160L, 2035588089L, 1423636267L, 2039186588L, 
1456626378L, 198792127L, -1109098743L, -46651362L, -409986612L, 
-60165219L, 141061671L, 1970685008L, 272764142L, 1705437595L, 
917938173L, -1842402582L, 215858568L, -76469455L, -1219959901L, 
-538008668L, 846622290L, -1830040153L, 1810655729L, -793453258L, 
-553998892L, 1776896869L, 1357181807L, -1458358257L)