knapsack problem

5 results back to index

Algorithms Unlocked by Thomas H. Cormen


bioinformatics, knapsack problem, NP-complete, optical character recognition, Silicon Valley, sorting algorithm, traveling salesman

Knapsack In the knapsack problem, we are given a set of n items, each with a weight and a value, and we ask whether there exists a subset of items whose total weight is at most a given weight W and whose total value is at least a given value V . This problem is the decision version of an optimization problem where we want to load up a knapsack with the most valuable subset of items, subject to not exceeding a weight limit. This optimization problem has obvious applications, such as deciding which items to take backpacking or what loot a burglar should choose to pilfer. The partition problem is really just a special case of the knapsack problem, in which the value of each item equals its weight and both W and V equal half the total weight. If we could solve the knapsack problem in polynomial time, then we could solve the partition problem in polynomial time.

If we could solve the knapsack problem in polynomial time, then we could solve the partition problem in polynomial time. Therefore, the knapsack problem is at least as hard as the partition problem, and we don’t even need to go through the full reduction process to show that the knapsack problem is NP-complete. General strategies As you have probably realized by now, there is no one-size-fits-all way to reduce one problem to another in order to prove NP-hardness. Some reductions are pretty simple, such as reducing the hamiltonian-cycle problem to the traveling-salesman problem, and some are extremely complicated. Here are a few things to remember and some strategies that often help. 206 Chapter 10: Hard? Problems Go from general to specific When reducing problem X to problem Y, you always have to start with an arbitrary input to problem X.

The hamiltonian-cycle problem is more restricted because each edge has only one of two “values”: present or absent. Look for special cases Several NP-complete problems are just special cases of other NPcomplete problems, much as the partition problem is a special case of Chapter 10: Hard? Problems 207 the knapsack problem. If you know that problem X is NP-complete and that it’s a special case of problem Y, then problem Y must be NPcomplete as well. That is because, as we saw for the knapsack problem, a polynomial-time solution for problem Y would automatically give a polynomial-time solution for problem X. More intuitively, problem Y, being more general than problem X, is at least as hard. Select an appropriate problem to reduce from It’s often a good strategy to reduce from a problem in the same, or at least a related, domain as the problem you’re trying to prove NPcomplete.


pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths


4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

The second, Continuous Relaxation, turns discrete or binary choices into continua: when deciding between iced tea and lemonade, first imagine a 50–50 “Arnold Palmer” blend and then round it up or down. The third, Lagrangian Relaxation, turns impossibilities into mere penalties, teaching the art of bending the rules (or breaking them and accepting the consequences). A rock band deciding which songs to cram into a limited set, for instance, is up against what computer scientists call the “knapsack problem”—a puzzle that asks one to decide which of a set of items of different bulk and importance to pack into a confined volume. In its strict formulation the knapsack problem is famously intractable, but that needn’t discourage our relaxed rock stars. As demonstrated in several celebrated examples, sometimes it’s better to simply play a bit past the city curfew and incur the related fines than to limit the show to the available slot. In fact, even when you don’t commit the infraction, simply imagining it can be illuminating.

(In formal notation: “Since 1|rj|∑ Cj is NP-hard, does that imply that 1|pmtn, rj|∑ Cj is NP-hard, too?” “No, that’s easy, remember?” “Well, 1|dj|∑ Cj is easy and that implies 1|pmtn, dj|∑ Cj is easy, so what do we know about 1|pmtn, rj, dj|∑ Cj?” “Nothing” [Lawler et al., “A Gift for Alexander!”; see also Lawler, “Old Stories”].) the problem becomes intractable: In fact, it’s equivalent to the “knapsack problem,” computer science’s most famously intractable problem about how to fill space. The connection between this scheduling problem and the knapsack problem appears in Lawler, Scheduling a Single Machine to Minimize the Number of Late Jobs. a certain time to start some of your tasks: What we are calling “start times” are referred to in the literature (we think somewhat ambiguously) as “release times.” Lenstra, Rinnooy Kan, and Brucker, “Complexity of Machine Scheduling Problems,” showed that both minimizing sum of completion times and minimizing maximal lateness with arbitrary release times are NP-hard.

.; networking; websites fast connections geography of infrastructure of protocols and security and interrupt coalescing interruptions intractable problems defined equilibrium and relaxation and scheduling and Introduction to Relaxation Methods, An (Shaw) intuitive hunches investment strategies invitations involuntary selflessness Jacobson, Van Jain, Kamal James, William Jarvis, Richard Jaws (film) Jay, Francine Jeffreys, Harold Jet Propulsion Laboratory (JPL) jitter Jobs, Steve job search Johnson, Selmer Jones, William Joy of Less, The (Jay) judgment “just play the game” approach just society Kaelbling, Leslie Kahn, Robert “Bob” Kant, Immanuel Karels, Michael Karp, Richard Kaushik, Avinash Kayal, Neeraj Keats, John Keeping Found Things Found (Jones) Kenney, Richard Kepler, Johannes Kerr, Clark Keynes, John Maynard al-Khwārizmī King County Library System (KCLS) king of the hill Kipling, Rudyard Kirkpatrick, Scott Kleinrock, Leonard Kline, Charley knapsack problem Knuth, Donald Koomen, Pete Ladder tournaments Lagrange, Joseph-Louis Lagrangian Relaxation Lai, Tze Leung lancet liver fluke Lange, Rebecca language Lao Tzu Laplace, Pierre-Simon Laplace’s Law Lasso latency lateness, minimizing maximum laundry law enforcement Lawler, Eugene “Gene” “Lawn Tennis Tournaments” (Dodgson) Law of Gross Tonnage Lawrence, Peter A. Lawrence Berkeley Laboratory (LBL) lawsuits Lazzarini, Mario Least Recently Used (LRU) Lee, Michael left-side insertion rule Le Guin, Ursula K.


pages: 229 words: 67,599

The Logician and the Engineer: How George Boole and Claude Shannon Created the Information Age by Paul J. Nahin


Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Any sufficiently advanced technology is indistinguishable from magic, Claude Shannon: information theory, conceptual framework, Fellow of the Royal Society, finite state, four colour theorem, Georg Cantor, Grace Hopper, Isaac Newton, John von Neumann, knapsack problem, New Journalism, reversible computing, Richard Feynman, Richard Feynman, Schrödinger's Cat, Steve Jobs, Steve Wozniak, thinkpad, Turing machine, Turing test, V2 rocket

That is, a quantum computer actually follows a multitude of superimposed, parallel computational paths (a process called quantum interference) to arrive at its final result. Such massive parallelism is the fundamental origin of the quantum computer’s phenomenal speed. A class of famous, easy-to-understand problems (quite different from the factoring and search problems) that could also benefit from the massive parallelism of a quantum computer are the so-called knapsack problems. They are old problems, dating back at least to 1897, but they have modern applications, including cryptography. One knapsack problem asks the following question: given a stretchable knapsack that can hold a maximum weight of W, and n objects of individual weights w1, W2,…, wn, is there a subset of these objects that can be put into the knapsack that just achieves the knapsack’s weight capacity? That is, is there a solution for the xi in the equation where xi = 0 or 1 for 1 ≤ i ≤ n?

See also error detection Hartley, Ralph Hermite, Charles Hermitian matrix Hilbert, David Hopper, Grace Huxley, Thomas identity matrix infinity: countable; uncountable invertor gate, quantum. See also NOT “Investigation of the Laws of Thought, An” (Boole) irreversible: computation; logic gate J-K flip-flop Jobs, Steve Karnaugh, Maurice; map of Kelland, Philip Kelly, Jr., John Kelvin, Lord. See Thomson, William Kirchhoff, Gustav; circuit laws of knapsack problems Landauer, Rolf Laplace, Pierre-Simon latch Leibniz, Gottfried Levor, Norma logical operations: and; exclusive-or; inclusive-or; NOT. See also switch logic gates: irreversible; reversible. See also gates, logic “Logic of Chance” (Venn) machine (asynchronous); synchronous) majority logic map method. See Karnaugh map “Mathematical Analysis of Logic” (Boole) “Mathematical Theory of Communication, A” (Shannon) matrix.


pages: 470 words: 144,455

Secrets and Lies: Digital Security in a Networked World by Bruce Schneier


Ayatollah Khomeini, barriers to entry, business process, butterfly effect, cashless society, Columbine, defense in depth, double entry bookkeeping, fault tolerance, game design, IFF: identification friend or foe, John von Neumann, knapsack problem, mutually assured destruction, pez dispenser, pirate software, profit motive, Richard Feynman, Richard Feynman, risk tolerance, Silicon Valley, Simon Singh, slashdot, statistical model, Steve Ballmer, Steven Levy, the payments system, Y2K, Yogi Berra

But given a single product, it can be impracticable to factor the number and recover the two factors. This is the kind of math that can be used to create public-key cryptography; it involves modular arithmetic, exponentiation, and large prime numbers thousands of bits long, but you can elide the details. Today, there are a good half-dozen algorithms, with names like RSA, ElGamal, and elliptic curves. (Algorithms based on something called the knapsack problem were another early contender, but over the course of about 20 years they were broken every which way.) The mathematicals are different for each algorithm, but conceptually they are all the same. Instead of a single key that Alice and Bob share, there are two keys: one for encryption and the other for decryption. The keys are different, and it is not possible to compute one key from the other.


pages: 489 words: 148,885

Accelerando by Stross, Charles


call centre, carbon-based life, cellular automata, cognitive dissonance, Conway's Game of Life, dark matter, dumpster diving, Extropian, finite state, Flynn Effect, glass ceiling, gravity well, John von Neumann, knapsack problem, Kuiper Belt, Magellanic Cloud, mandelbrot fractal, market bubble, means of production, packet switching, performance metric, phenotype, planetary scale, Pluto: dwarf planet, reversible computing, Richard Stallman, SETI@home, Silicon Valley, Singularitarianism, slashdot, South China Sea, stem cell, technological singularity, telepresence, The Chicago School, theory of mind, Turing complete, Turing machine, Turing test, upwardly mobile, Vernor Vinge, Von Neumann architecture, web of trust, Y2K

He's not sure Pamela ever let him see her fully naked: She thought skin was more sexy when it was covered. Annette squeezes him again, and he stiffens. "More!" By the time they finish, he's aching, and she shows him how to use the bidet. Everything is crystal clear, and her touch is electrifying. While she showers, he sits on the toilet seat lid and rants about Turing-completeness as an attribute of company law, about cellular automata and the blind knapsack problem, about his work on solving the Communist Central Planning problem using a network of interlocking unmanned companies. About the impending market adjustment in integrity, the sinister resurrection of the recording music industry, and the still-pressing need to dismantle Mars. When she steps out of the shower, he tells her that he loves her. She kisses him and slides his glasses and earpieces off his head so that he's really naked, sits on his lap, and fucks his brains out again, and whispers in his ear that she loves him and wants to be his manager.