knapsack problem
(redirected from 0-1 knapsack problem)

Also found in: Wikipedia

0.01 sec.

knapsack problem [′nap‚sak ‚präb·ləm]

(mathematics)

The problem, given a set of integers {A₁,A₂, …,A_n} and a target integerB, of determining whether a subset of theA_ican be selected without repetition so that their sum is the targetB.

(application, mathematics)

knapsack problem - Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible.

The 0/1 knapsack problem restricts the number of each items to zero or one.

Such constraint satisfaction problems are often solved using dynamic programming.

The general knapsack problem is NP-hard, and this has led to attempts to use it as the basis for public-key encryption systems. Several such attempts failed because the knapsack problems they produced were in fact solvable by polynomial-time algorithms.

Want to thank TFD for its existence? Tell a friend about us, add a link to this page, add the site to iGoogle, or visit the webmaster's page for free fun content.

?Page tools

Printer friendly
Cite / link

Feedback

Mentioned in	?		References in periodicals archive	?		Encyclopedia browser	?		Full browser	?
No references found			The authors characterize the tax planning problem as a 0-1 knapsack problem and employ PROC LP to optimize the overall tax burden. Sheltering your profits: how owners of small businesses and ... by Gibley, Raymond A.; Gibley, Janet R. / The National Public Accountant			Žemaite, Julija Žemaitija Uplands Žeran Žermena Heine-Vagnere Žižka, Jan Žiguri Žilina Žiugžda, Juozas Žiugžda, Juozas Ionovich Živkovic, Petar Živojin Žujovic Živojin Jocic Žmud Horse Žmuidzinavicius, Antanas Jono Žujovic, Živojin Žukas, Stepas Adolfo Župa Župancic, Oton Žuvintas Žyrardów, Strike of 1883 žanis Griva £ 0 0 Canada! national song of Canada 0 Deutschland, Hoch in Ehren! 0-1 knapsack problem 0/1 knapsack problem 0K 0x 1 1, 2, 3-Benzotriazole 1,1,1-chlorodifluoroethane 1,1,2-trichloro-1,2,2-trifluoroethane 1,1-diethoxyethane 1,2,3,4,5,6-hexachlorocyclohexane 1,2,3-benzotriazole 1,2,3-trichloropropane 1,2,4-benzenetricarboxylic acid 1,2,4-benzenetriol 1,2-benzopyrone 1,2-butylene oxide 1,2-epoxyethane 1,2-ethanedithiol 1,2-naphthoquinone 1,3-butadiene 1,3-butylene glycol 1,3-cyclohexadiene 1,3-cyclopentadiene 1,3-dichloro-2-propanol 1,4-butylene glycol 1,4-dichlorobutane			¾ ¾ × × × Cuprocyparis leylandii × Cuprocyparis leylandii ÷ 0 0 0 0 (disambiguation) 0 (disambiguation) 0 (number) 0 (number) 0 Canada! national song of Canada 0 Deutschland, Hoch in Ehren! 0 divided by 0 0 K 0 K 0 K 0 Kelvin 0 Kelvin 0 Kelvin 0 vector 0%$ 0-0 0-0 0-1 integer programming 0-1 integer programming 0-1 integer programming 0-1 knapsack problem 0-9 0-9 0-based 0-based 0-based indexing 0-based indexing 0-based indexing 0-based indexing 0-based indexing 0-Chlorobenzylmalononitrile 0-d 0-d 0-d 0-d 0-form 0-Kills 0-polytope 0. 0. 0.09 process 0.1 0.1 0.13 process 0.13 process 0.13 process 0.18 process 0.18 process 0.18 process 0.25 0.25

Encyclopedia

Free Tools:	For surfers: Free toolbar & extensions \| Word of the Day \| Help For webmasters: Free content \| Linking \| Lookup box \| Double-click lookup

Disclaimer
All content on this website, including dictionary, thesaurus, literature, geography, and other reference data is for informational purposes only. This information should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional.

knapsack problem (redirected from 0-1 knapsack problem)

knapsack problem
(redirected from 0-1 knapsack problem)