732A94lab6: Knapsack Problem Algorithms

.Random.seed <-
c(10403L, 10L, -1314444539L, 923036604L, -297206126L, 162143629L, 
729959879L, 300166830L, -128678136L, -1757981429L, -1258806295L, 
1301107896L, -484211866L, 717498369L, -317344109L, 193300802L, 
-596482316L, -1477479689L, -1721589011L, -1642267260L, -471387222L, 
1803651349L, -952106065L, 2029509558L, 1277542880L, 1920065827L, 
-476817855L, -376415952L, 303819598L, 1371632057L, 552020939L, 
-1812832134L, -1455750788L, 228364735L, -1898369387L, 1992332460L, 
68632194L, 878663261L, 1925396823L, 1479550014L, 1909663864L, 
-583601317L, -1417662791L, 690496264L, -365405770L, -2063374607L, 
-2104807133L, -1657560206L, 1782909380L, -864980601L, 1253198685L, 
-702216876L, 877291386L, 221775557L, -774977505L, -90673242L, 
-1049472720L, 1069468627L, 348000753L, 1988949792L, 2022621630L, 
-958942775L, -240589445L, 1868288842L, 301372332L, -1585071441L, 
723241061L, 526952476L, -1949145486L, 259127533L, 229161255L, 
1550411086L, -2146867800L, 317809067L, -1325638967L, 1221282520L, 
103954310L, -243062175L, 922514419L, 1356981858L, 1444298964L, 
37915095L, 473971661L, 299503460L, 155097930L, -1679005003L, 
301455887L, -685130986L, 472798656L, 726238595L, 1263242145L, 
928256912L, -1903701906L, 1701787161L, 893146795L, -1844565350L, 
725653084L, 949338975L, 1863253301L, -144200500L, -1259039198L, 
-1115019139L, -1763585673L, 1988542110L, -263705256L, -1940284229L, 
-1619549607L, 486328808L, -492737514L, -587655279L, -1856374717L, 
-155189422L, 240780260L, -356820441L, -2134822275L, -1940067468L, 
-1275279526L, -1371618907L, 1284890047L, 1264909894L, 1064094928L, 
-1646385421L, -1749917679L, -817625536L, -175248866L, -1081252631L, 
970575387L, -659673558L, 1958154572L, 846863119L, 407014981L, 
-823003140L, 1613770322L, -1091013683L, -405226105L, 471070830L, 
-1302527928L, 1723626059L, 167391145L, 973397752L, 1405925926L, 
-2120436927L, 763762899L, -1003152254L, -1714414924L, 1489243703L, 
2145842477L, -1114145212L, -889830550L, -1112272939L, -1165223569L, 
1866249334L, -768041056L, 553535587L, -1582985983L, 878428272L, 
527748110L, -1690620807L, 352680971L, -876808902L, -968735684L, 
-339815553L, -1650138923L, -2005003028L, -203379134L, -1207656035L, 
-1574366185L, 1412286846L, 1184042808L, 1064749083L, 717965689L, 
514469832L, 187986934L, 643671601L, -1178115997L, 1618714674L, 
1077419396L, -875577L, 731088541L, -2137625068L, 1151792314L, 
-837558011L, 1561068255L, -795119770L, 1842923248L, -1290174957L, 
-751462479L, -1029348768L, 1241358334L, 1328959369L, 1282427067L, 
-1854004086L, 1637463916L, -30489361L, -1358893275L, 932223452L, 
-1345189966L, 866979501L, 527410791L, 945444238L, -1695784344L, 
567303787L, -1900021751L, 218769048L, 699867590L, -1923419871L, 
-658783821L, 2103803170L, 875132692L, 2010001303L, -374362227L, 
-602041692L, -1688855414L, -1811950859L, -420367025L, 911508054L, 
114319616L, 1548588099L, 925284321L, -1019029680L, -90748498L, 
-558151847L, 297880939L, 594679002L, -1047290468L, -1552662113L, 
217220085L, -419835252L, 1586034530L, -1013544198L, -1225033904L, 
-1878000596L, -333679244L, 108119698L, -1115522464L, -148405620L, 
1977154400L, -407936286L, -122535768L, -1013022516L, -403109380L, 
-713830478L, -975464976L, -538622524L, 1323786072L, -862983302L, 
1648612784L, -785131076L, -1661884332L, -523228222L, -1995078880L, 
370474940L, -1668494768L, -2016035358L, 2113605992L, 1462734156L, 
-219412228L, 637461234L, 1693308672L, -230619532L, -292607992L, 
-28280390L, -1050732592L, 876616172L, -1485910124L, 221360850L, 
-1863520672L, 976422220L, 373134624L, -568487294L, -1640420888L, 
-646543380L, 1774679612L, -1685803406L, 1070703472L, 1015900452L, 
423178808L, 1158480282L, 1391217104L, 516513212L, -1142380396L, 
-1176306558L, 2101331392L, -801176772L, -1130941296L, 971645730L, 
-1437585912L, 1727999244L, 154047900L, -1994285550L, -1969861760L, 
1158226708L, 100454696L, 2092133434L, -1599902768L, -1581464980L, 
-344606156L, 1879448210L, -473981600L, -223393460L, -406562848L, 
-481127006L, -1557365336L, 1028728460L, 263699900L, 1456778866L, 
-1198474256L, 720057924L, -137922472L, 1191106618L, -927618960L, 
1873836092L, 1200355604L, 1941734082L, 746884832L, 2002151548L, 
-630796592L, 538745250L, -587583448L, -692053236L, -1638641220L, 
701698866L, 1555700416L, 2143265844L, -640690488L, 1591047354L, 
842495632L, -296882452L, 1861528148L, -2100165998L, -861519584L, 
-218551860L, 1019282144L, -1776166718L, -589204440L, -704317524L, 
1756463804L, -1251488782L, 1301753392L, 1425565604L, 1154641336L, 
-721868966L, 175550608L, -1814092932L, 72339732L, 158091586L, 
-1744410368L, 1576193468L, 80939344L, -89855710L, 1601880648L, 
-1393563636L, 1764574812L, 302967250L, 1908379136L, 1850973524L, 
-615789336L, 1999407354L, 1338728144L, 1699973932L, 574630132L, 
-782851694L, -967457440L, -1028541428L, -1723659040L, 295342690L, 
-1880480600L, 1661912140L, 1912643452L, 744339762L, 415736432L, 
-1812778172L, -789218344L, 1083190138L, 1565440048L, -1399291972L, 
948906580L, -1278283710L, -1884485984L, -1265499460L, -2076130352L, 
-2030365342L, -1045201176L, 18373836L, 1933072892L, 835214834L, 
1447206016L, -631637516L, 437535368L, -83297478L, 5907792L, -1216773012L, 
2129989012L, -2070446L, -590840352L, 1859531980L, -653386080L, 
38982018L, -283270936L, 475122412L, -1600086724L, -1572190094L, 
-632167824L, 466868772L, 2053892152L, 777304346L, 1741710544L, 
1514084668L, 1757565844L, 1967085442L, 1750977472L, 1884476988L, 
287572368L, -405886942L, 894602504L, 1945036940L, -1608020196L, 
1093500050L, 721898880L, 1703505940L, 1143908136L, -52353478L, 
-2101638704L, -1487666836L, -1037075532L, 1469993490L, -2033362976L, 
-750061108L, -215148320L, -1988955102L, -1594262744L, 260860428L, 
944550716L, -2124085262L, -371539216L, 1648446020L, -685722024L, 
-1613064390L, 224630768L, -1736119620L, 911377684L, -1037603646L, 
-302420896L, 637025660L, -1782218800L, 1637796130L, 347737768L, 
-1349124212L, 725509308L, 1624380210L, -1663257024L, -172215116L, 
1687522376L, 363433402L, 1140988432L, 165596396L, 1447025811L, 
-873925643L, 1644549586L, -941578720L, -1124268023L, -733647557L, 
165109900L, 87543066L, 1969947535L, -739361575L, 2101629806L, 
-1845656836L, 1271476333L, -1021879273L, 1690869216L, 1772227006L, 
1532043147L, 628793357L, 562137146L, -713021320L, 1783186465L, 
-92809517L, -1257019916L, -244676990L, 519643927L, 478196193L, 
-1182220506L, -1324848604L, -449426219L, 462306431L, 1781641496L, 
-1548033994L, 1881323203L, -999998715L, -1107747166L, -77779824L, 
-819004359L, -121678613L, -1523857956L, 1997597706L, 514722559L, 
-1700043959L, 569301214L, 1156302476L, 553546333L, 768102503L, 
-424473200L, 690240942L, -861689765L, 1334534205L, -177506646L, 
-1548102840L, 2022446961L, 721092835L, 41949156L, -1510142190L, 
-629419289L, -1670261583L, -1302481162L, 1236558100L, 522294821L, 
-18994385L, -1215505176L, 430734790L, -1746187149L, -1831696683L, 
1677556914L, -1237159808L, -1398612887L, -1602131749L, 1778891820L, 
-1855568838L, 889180911L, -1021293191L, -581492210L, 737874908L, 
-344023987L, -1590161481L, -1570410176L, -1405003746L, -442036501L, 
-1277272467L, -1314371878L, 171947672L, -1706164991L, 439304883L, 
-484766252L, -1738781470L, -88283785L, -798466879L, 578461766L, 
-1276440700L, -1998264011L, 1357805343L, -239576456L, -719503530L, 
-474096157L, 1777447845L, 740409922L, 151003184L, 1877431385L, 
-319649333L, 284314172L, 976749674L, 1314936479L, -491300055L, 
896268222L, 1365313196L, 181529597L, 156377927L, -318700496L, 
947840334L, 1877327227L, 1898277597L, 341781258L, 432679464L, 
-1121140079L, -253427069L, -1292909692L, 1842358706L, 44209927L, 
388117841L, 1594129622L, 764467636L, -942043707L, 812358927L, 
-1182717048L, -408702298L, -1128193453L, 294644661L, -738502382L, 
1226181344L, 1033264969L, -1925910149L, 456006732L, -1533190694L, 
-1359814705L, -1441373799L, -978218578L, 807710396L, -1978163411L, 
947739863L, 967370016L, -330747266L, -441254837L, 543452749L, 
1262474362L, 155014328L, 831250017L, -493181933L, 102355508L, 
-1607412670L, 1769270359L, -760027231L, -28731290L, 1178198116L, 
-1431913579L, 592563391L, 1217936472L, 2057906294L, 589027459L, 
481138885L, 1793676770L, 851287120L, 1907324281L, -352826709L, 
-1184329188L, -2047611574L, -873245377L, 784762293L)