About: Knapsack problem

content	<p>Your browser does not support iframes.</p>
og:image	https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Knapsack_Problem_Illustration.svg/800px-Knapsack_Problem_Illustration.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Knapsack_Problem_Illustration.svg/1200px-Knapsack_Problem_Illustration.svg.png https://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Knapsack_Problem_Illustration.svg/640px-Knapsack_Problem_Illustration.svg.png
og:image:height	693 1040 554
og:image:width	800 1200 640
og:title	Knapsack problem - Wikipedia
og:type	website
Title	Knapsack problem - Wikipedia
links to	https://en.wikipedia.org/wiki/CiteSeerX_(identifier) https://en.wikipedia.org/wiki/Parallel_computing https://en.wikipedia.org/wiki/Portal:Computer_programming https://en.wikipedia.org/wiki/Cryptography https://search.worldcat.org/issn/0097-5397 https://en.wikipedia.org/wiki/Greatest_common_divisor https://arxiv.org/abs/1302.5843 https://en.wikipedia.org/wiki/Fixed_investment https://en.wikipedia.org/wiki/Sartaj_Sahni https://en.wikipedia.org/wiki/Combinatorial_optimization https://en.wikipedia.org/wiki/Approximation_algorithm https://en.wikipedia.org/wiki/Branch_and_bound https://search.worldcat.org/issn/2296-424X https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem https://search.worldcat.org/issn/1432-0541 https://wikimediafoundation.org/ https://donate.wikimedia.org/?wmf_sour..._campaign=en.wikipedia.org&uselang=en https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy https://foundation.wikimedia.org/wiki/...uage/Policy:Universal_Code_of_Conduct https://developer.wikimedia.org https://stats.wikimedia.org/#/en.wikipedia.org https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement https://www.mediawiki.org/ https://en.wikipedia.org/wiki/Wayback_Machine https://en.wikipedia.org/wiki/ISBN_(identifier) https://en.wikipedia.org/wiki/Doi_(identifier) https://en.wikipedia.org/wiki/Category:Webarchive_template_wayback_links https://en.wikipedia.org/wiki/S2CID_(identifier) https://en.wikipedia.org/wiki/Category:CS1:_long_volume_value https://en.wikipedia.org/wiki/Hdl_(identifier) https://en.wikipedia.org/wiki/JSTOR_(identifier) https://en.wikipedia.org/wiki/Category:Use_dmy_dates_from_April_2020 https://en.wikipedia.org/wiki/Category..._a_fallback_via_Module:Annotated_link https://en.wikipedia.org/wiki/Category...ect_targets_via_Module:Annotated_link https://en.wikipedia.org/wiki/Hamiltonian_(quantum_mechanics) https://en.wikipedia.org/wiki/Real_number https://en.wikipedia.org/wiki/Main_Page https://en.wikipedia.org/wiki/Wikipedia:Contents https://en.wikipedia.org/wiki/Portal:Current_events https://en.wikipedia.org/wiki/Special:Random https://en.wikipedia.org/wiki/Wikipedia:About https://en.wikipedia.org/wiki/Wikipedia:Contact_us https://en.wikipedia.org/wiki/Help:Contents https://en.wikipedia.org/wiki/Help:Introduction https://en.wikipedia.org/wiki/Wikipedia:Community_portal https://en.wikipedia.org/wiki/Special:RecentChanges https://en.wikipedia.org/wiki/Wikipedia:File_upload_wizard https://en.wikipedia.org/wiki/Special:Search https://en.wikipedia.org/wiki/Special:MyContributions https://en.wikipedia.org/wiki/Special:MyTalk https://en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard https://en.wikipedia.org/wiki/Special:SpecialPages https://en.wikipedia.org/wiki/ISSN_(identifier) https://en.wikipedia.org/wiki/Help:Category https://en.wikipedia.org/wiki/Category:Articles_with_short_description https://en.wikipedia.org/wiki/Category:Short_description_matches_Wikidata https://en.wikipedia.org/wiki/Wikipedi...-ShareAlike_4.0_International_License https://en.wikipedia.org/wiki/Wikipedia:General_disclaimer https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/ArXiv_(identifier) https://en.wikipedia.org/wiki/Bibcode_(identifier) https://arxiv.org/archive/cs.DS https://en.wikipedia.org/wiki/Fixed-point_arithmetic https://en.wikipedia.org/wiki/George_Dantzig https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Meet-in-the-middle_attack https://en.wikipedia.org/wiki/Public-key_cryptography https://en.wikipedia.org/wiki/Category:Cryptography https://en.wikipedia.org/wiki/Portfolio_(finance) https://en.wikipedia.org/wiki/Securitization https://en.wikipedia.org/wiki/Decision_tree_model https://en.wikipedia.org/wiki/Investment https://www.wikimedia.org/ https://en.wikipedia.org/wiki/Resource_allocation https://en.wikipedia.org/wiki/Greedy_algorithm https://en.wikipedia.org/wiki/Suffix_tree https://en.wikipedia.org/wiki/P_versus_NP_problem https://search.worldcat.org/issn/0304-3975 https://search.worldcat.org/issn/0196-6774 https://en.wikipedia.org/wiki/List_of_knapsack_problems https://en.wikipedia.org/wiki/Packing_problem https://en.wikipedia.org/wiki/MR_(identifier) https://en.wikipedia.org/wiki/Quantum_computation https://en.wikipedia.org/wiki/Combinatorial_auction https://en.wikipedia.org/wiki/Affine_function https://en.wikipedia.org/wiki/Linear_programming_relaxation https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems https://en.wikipedia.org/wiki/Gekko_(optimization_software) https://en.wikipedia.org/wiki/Michael_R._Garey https://en.wikipedia.org/wiki/David_S._Johnson https://en.wikipedia.org/wiki/Computer...uide_to_the_Theory_of_NP-Completeness https://en.wikipedia.org/wiki/Special:BookSources/978-0-7167-1045-5 https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/NP-complete https://en.wikipedia.org/wiki/Decision_problem https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme https://en.wikipedia.org/wiki/Category:Combinatorial_optimization https://en.wikipedia.org/wiki/Bin_packing_problem https://en.wikipedia.org/wiki/Cutting_stock_problem https://doi.org/10.1007%2F978-3-540-24777-7 https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-40286-2 https://api.semanticscholar.org/CorpusID:28836720 https://search.worldcat.org/issn/0163-5700 https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Co-NP-complete https://en.wikipedia.org/wiki/Strongly_NP-complete https://en.wikipedia.org/wiki/Category:NP-complete_problems https://en.wikipedia.org/wiki/Pseudo-polynomial_time https://en.wikipedia.org/wiki/Baby-step_giant-step https://en.wikipedia.org/wiki/Quadratic_knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem#bodyContent https://en.wikipedia.org/w/index.php?t...eateAccount&returnto=Knapsack+problem https://en.wikipedia.org/w/index.php?t...l:UserLogin&returnto=Knapsack+problem https://en.wikipedia.org/wiki/Knapsack_problem# https://en.wikipedia.org/wiki/Knapsack_problem#Applications https://en.wikipedia.org/wiki/Knapsack_problem#Definition https://en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity https://en.wikipedia.org/wiki/Knapsack_problem#Unit-cost_models https://en.wikipedia.org/wiki/Knapsack_problem#Solving https://en.wikipedia.org/wiki/Knapsack...amic_programming_in-advance_algorithm https://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle https://en.wikipedia.org/wiki/Knapsack_problem#Approximation_Algorithms https://en.wikipedia.org/wiki/Knapsack_problem#Greedy_approximation_algorithm https://en.wikipedia.org/wiki/Knapsack..._polynomial_time_approximation_scheme https://en.wikipedia.org/wiki/Knapsack_problem#Quantum_approximate_optimization https://en.wikipedia.org/wiki/Knapsack_problem#Dominance_relations https://en.wikipedia.org/wiki/Knapsack_problem#Variations https://en.wikipedia.org/wiki/Knapsack_problem#Multi-dimensional_objective https://en.wikipedia.org/wiki/Knapsack_problem#Multi-dimensional_weight https://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsacks https://en.wikipedia.org/wiki/Knapsack_problem#Quadratic https://en.wikipedia.org/wiki/Knapsack_problem#Geometric https://en.wikipedia.org/wiki/Knapsack_problem#Online https://en.wikipedia.org/wiki/Knapsack_problem#See_also https://en.wikipedia.org/wiki/Knapsack_problem#Notes https://en.wikipedia.org/wiki/Knapsack_problem#References https://en.wikipedia.org/wiki/Knapsack_problem#External_links https://ar.wikipedia.org/wiki/%D9%85%D...%D8%A9_%D8%A7%D9%84%D8%B8%D9%87%D8%B1 https://bg.wikipedia.org/wiki/%D0%97%D...0%D0%BD%D0%B8%D1%86%D0%B0%D1%82%D0%B0 https://ca.wikipedia.org/wiki/Problema_de_la_motxilla https://cs.wikipedia.org/wiki/Probl%C3%A9m_batohu https://da.wikipedia.org/wiki/Rygs%C3%A6kproblem https://de.wikipedia.org/wiki/Rucksackproblem https://es.wikipedia.org/wiki/Problema_de_la_mochila https://eu.wikipedia.org/wiki/Bizkar-zorroaren_buruketa https://fa.wikipedia.org/wiki/%D9%85%D...9%87%E2%80%8C%D9%BE%D8%B4%D8%AA%DB%8C https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C https://hy.wikipedia.org/wiki/%D5%88%D...%D5%AB_%D5%AD%D5%B6%D5%A4%D5%AB%D6%80 https://it.wikipedia.org/wiki/Problema_dello_zaino https://he.wikipedia.org/wiki/%D7%91%D...%D7%9E%D7%99%D7%9C_%D7%94%D7%92%D7%91 https://ka.wikipedia.org/wiki/%E1%83%9...D%E1%83%AA%E1%83%90%E1%83%9C%E1%83%90 https://lv.wikipedia.org/wiki/Uzdevums_par_mugursomu https://nl.wikipedia.org/wiki/Knapzakprobleem https://ja.wikipedia.org/wiki/%E3%83%8...5%E3%83%83%E3%82%AF%E5%95%8F%E9%A1%8C https://pl.wikipedia.org/wiki/Problem_plecakowy https://pt.wikipedia.org/wiki/Problema_da_mochila https://ro.wikipedia.org/wiki/Problema_rucsacului https://ru.wikipedia.org/wiki/%D0%97%D...0%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B5 https://sl.wikipedia.org/wiki/Preprosti_problem_nahrbtnika https://sr.wikipedia.org/wiki/Problem_ranca https://sv.wikipedia.org/wiki/Kapps%C3%A4cksproblemet https://th.wikipedia.org/wiki/%E0%B8%9...3%E0%B8%B0%E0%B8%AA%E0%B8%AD%E0%B8%9A https://tr.wikipedia.org/wiki/S%C4%B1rt_%C3%A7antas%C4%B1_problemi https://uk.wikipedia.org/wiki/%D0%97%D...0%D1%8E%D0%BA%D0%B7%D0%B0%D0%BA%D0%B0 https://vi.wikipedia.org/wiki/B%C3%A0i_to%C3%A1n_x%E1%BA%BFp_ba_l%C3%B4 https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98 https://www.wikidata.org/wiki/Special:EntityPage/Q864457#sitelinks-wikipedia https://en.wikipedia.org/wiki/Talk:Knapsack_problem https://en.wikipedia.org/w/index.php?title=Knapsack_problem&action=edit https://en.wikipedia.org/w/index.php?title=Knapsack_problem&action=history https://en.wikipedia.org/wiki/Special:WhatLinksHere/Knapsack_problem https://en.wikipedia.org/wiki/Special:RecentChangesLinked/Knapsack_problem https://en.wikipedia.org/w/index.php?title=Knapsack_problem&oldid=1283814254 https://en.wikipedia.org/w/index.php?title=Knapsack_problem&action=info https://en.wikipedia.org/w/index.php?t...1283814254&wpFormIdentifier=titleform https://en.wikipedia.org/w/index.php?t...kipedia.org%2Fwiki%2FKnapsack_problem https://en.wikipedia.org/w/index.php?t...kipedia.org%2Fwiki%2FKnapsack_problem https://en.wikipedia.org/w/index.php?t...k_problem&action=show-download-screen https://en.wikipedia.org/w/index.php?title=Knapsack_problem&printable=yes https://www.wikidata.org/wiki/Special:EntityPage/Q864457 https://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints https://en.wikipedia.org/wiki/Knapsack https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-1 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-2 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=1 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-3 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-4 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-5 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-6 https://en.wikipedia.org/wiki/Knapsack_cryptosystems https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-7 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-8 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=2 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=3 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-pisinger200308-9 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-Cacetta2001-10 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-poirriez_et_all_2009-11 https://en.wikipedia.org/wiki/Weakly_NP-complete https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-Wojtczak18-12 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=4 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-13 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-14 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-15 https://en.wikipedia.org/wiki/Rationals https://en.wikipedia.org/wiki/Real_RAM https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-16 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-17 https://en.wikipedia.org/wiki/Knapsack_problem#Subset-sum_problem https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=5 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-eduk2000-18 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-martellototh90-19 https://en.wikipedia.org/wiki/Hybrid_algorithm https://en.wikipedia.org/wiki/Knapsack...#cite_note-martellopisingertoth99a-20 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-plateau85-21 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-martellotothe99-22 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=6 https://en.wikipedia.org/wiki/Pseudopolynomial https://en.wikipedia.org/wiki/Weak_NP-completeness https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=7 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=8 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-23 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-24 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-25 https://en.wikipedia.org/w/index.php?t...napsack_problem&action=edit§ion=9 https://en.wikipedia.org/wiki/Fully_polynomial_time_approximation_scheme https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-Vazirani,_Vijay_2003-26 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=10 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-dantzig1957-27 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-28 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=11 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=12 https://en.wikipedia.org/wiki/Quantum_approximate_optimization_algorithm https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-29 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=13 https://en.wikipedia.org/w/index.php?t...nance_relations&action=edit&redlink=1 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=14 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=15 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-30 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-31 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=16 https://en.wikipedia.org/wiki/EPTAS https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-32 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-CohenGrebla-33 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-34 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=17 https://en.wikipedia.org/wiki/Multiple_knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-35 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=18 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-QKP-36 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-37 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-38 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=19 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-39 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=20 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-40 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-41 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-42 https://en.wikipedia.org/wiki/Knapsack_problem#cite_note-43 https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=21 https://en.wikipedia.org/wiki/Change-making_problem https://en.wikipedia.org/wiki/Continuous_knapsack_problem https://en.wikipedia.org/wiki/Knapsack_auction https://en.wikipedia.org/w/index.php?t...apsack_problem&action=edit§ion=22 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-1 http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf https://doi.org/10.1112%2Fplms%2Fs1-28.1.486 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-2 https://web.archive.org/web/2019060803...7822859549cd6b12b0d1f76f8ee3680a0.pdf https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-3 https://books.google.com/books?id=u5DB7gck08YC https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-4 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-5 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-6 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-7 https://doi.org/10.1287%2Fmnsc.19.8.961 https://www.jstor.org/stable/2629127 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-8 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.8357 https://doi.org/10.1145%2F333623.333627 https://api.semanticscholar.org/CorpusID:15619060 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-pisinger200308_9-0 http://citeseerx.ist.psu.edu/viewdoc/d...?doi=10.1.1.87.7431&rep=rep1&type=pdf https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-Cacetta2001_10-0 https://doi.org/10.1016%2Fs0362-546x%2801%2900658-7 https://en.wikipedia.org/wiki/Knapsack...em#cite_ref-poirriez_et_all_2009_11-0 https://en.wikipedia.org/wiki/Knapsack...em#cite_ref-poirriez_et_all_2009_11-1 https://en.wikipedia.org/wiki/Knapsack...em#cite_ref-poirriez_et_all_2009_11-2 https://doi.org/10.1016%2Fj.disopt.2008.09.004 https://search.worldcat.org/issn/1572-5286 https://api.semanticscholar.org/CorpusID:8820628 https://en.wikipedia.org/wiki/Knapsack_problem#cite_ref-Wojtczak18_12-0 https://arxiv.org/abs/1802.09465 https://doi.org/10.1007%2F978-3-319-90530-3_26
opl:providedBy	http://www.stackoverflow.com/#this
xhv:alternate	http://dev.restore.ovi.cnr.it:8890/abo...title=Special:RecentChanges&feed=atom https://en.wikipedia.org/w/index.php?title=Special:RecentChanges&feed=atom https://en.m.wikipedia.org/wiki/Knapsack_problem http://dev.restore.ovi.cnr.it:8890/abo...hp?title=Knapsack_problem&action=edit http://dev.restore.ovi.cnr.it:8890/abo...m.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/w/index.php?title=Knapsack_problem&action=edit
xhv:icon
xhv:license	Deed - Attribution-ShareAlike 4.0 International - Creative Commons
xhv:stylesheet	http://dev.restore.ovi.cnr.it:8890/abo...ent.init&only=styles&skin=vector-2022 http://dev.restore.ovi.cnr.it:8890/abo...e.styles&only=styles&skin=vector-2022
mw:PageProp/toc