# knapsack problem

8 results back to index

Algorithms Unlocked by Thomas H. Cormen

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.

Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier

The idea behind the Merkle-Hellman knapsack algorithm is to encode a message as a solution to a series of knapsack problems. A block of plaintext equal in length to the number of items in the pile would select the items in the knapsack (plaintext bits corresponding to the b values), and the ciphertext would be the resulting sum. Figure 19.1 shows a plaintext encrypted with a sample knapsack problem. The trick is that there are actually two different knapsack problems, one solvable in linear time and the other believed not to be. The easy knapsack can be modified to create the hard knapsack. The public key is the hard knapsack, which can easily be used to encrypt but cannot be used to decrypt messages. The private key is the easy knapsack, which gives an easy way to decrypt messages. People who don’t know the private key are forced to try to solve the hard knapsack problem. Superincreasing Knapsacks What is the easy knapsack problem?

This is much more difficult than a superincreasing knapsack where, if you add one more weight to the sequence, it simply takes another operation to find the solution. Figure 19.1 Encryption with knapsacks. The Merkle-Hellman algorithm is based on this property. The private key is a sequence of weights for a superincreasing knapsack problem. The public key is a sequence of weights for a normal knapsack problem with the same solution. Merkle and Hellman developed a technique for converting a superincreasing knapsack problem into a normal knapsack problem. They did this using modular arithmetic. Creating the Public Key from the Private Key Without going into the number theory, this is how the algorithm works: To get a normal knapsack sequence, take a superincreasing knapsack sequence, for example {2, 3, 6, 13, 27, 52}, and multiply all of the values by a number n, mod m.

Good public-key protocols are designed so that the various parties can’t decrypt arbitrary messages generated by other parties—the proof-of-identity protocols are a good example (see Section 5.2). 19.2 Knapsack Algorithms The first algorithm for generalized public-key encryption was the knapsack algorithm developed by Ralph Merkle and Martin Hellman [713, 1074]. It could only be used for encryption, although Adi Shamir later adapted the system for digital signatures [1413]. Knapsack algorithms get their security from the knapsack problem, an NP-complete problem. Although this algorithm was later found to be insecure, it is worth examining because it demonstrates how an NP-complete problem can be used for public-key cryptography. The knapsack problem is a simple one. Given a pile of items, each with different weights, is it possible to put some of those items into a knapsack so that the knapsack weighs a given amount? More formally: Given a set of values M1, M2,..., Mn , and a sum S, compute the values of bi such that S = b1M1 + b2M2 + ...+ bnMn The values of bi can be either zero or one.

pages: 229 words: 67,599

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

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: 523 words: 143,139

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

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.

Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age by Steven Levy

With only a few packages to choose from, the optimal solution isn’t that tough to find, but if there are plenty of packages, it gets much harder. Since Merkle wanted these knapsacks to act as trapdoor one-way functions—something that would be easy for the right person to solve but nearly impossible for everyone else to crack—he needed to figure out a way to tame this difficult problem for the proper keyholder. He did this by first using a much easier variation of the knapsack problem called a superincreasing knapsack. In these problems, the list of weights is ordered in such a way that discovering the solution is a breeze. Merkle then figured out a way to transform that easy process to the far knottier problem that comes with figuring out the solution to a normal knapsack, where the weights aren’t so helpfully arranged. It was a complicated but logical process. Someone who wished to receive a private message would begin with her own superincreasing knapsack, which would essentially be her secret key.

“I’m offering \$100 to the first person to break it,” he wrote to Hellman. “I’ve discreetly shown it to a few people here, and after listening to the resulting silence, I’ve concluded that the solution, if it exists, is at least not embarrassingly simple.” To be sporting about it, he made the task immeasurably easier, asking potential crackers to solve the problem with the difficulty of the knapsack problem set at a level so low that Merkle knew that there was at least a remote chance that someone might collect the reward. After that, he figured, he could raise the stakes and offer a higher bounty if someone cracked the real thing. “The point was that no one gave a damn about this stuff,” he says. “I figured that if I offered money for the [possibly unbreakable] knapsack, people would just throw in the towel.

pages: 233 words: 67,596

Competing on Analytics: The New Science of Winning by Thomas H. Davenport, Jeanne G. Harris

To do so, it forecasts demand and capacity at the national level and fulfillment center level for each SKU. Its supply chain analysts try to optimize order quantities to satisfy constraints and minimize holding, shipping, and stock-out costs. In order to optimize its consumer goods supply chain, for example, it used an “integral min-cost flow problem with side constraints”; to round off fractional shipments, it used a “multiple knapsack problem using the greedy algorithm.” Logistics Management Sometimes a service company uses analytics with such skill and execution that entire lines of business can be created. United Parcel Service (UPS) took this route in 1986, when it formed UPS Logistics, a wholly owned subsidiary of UPS Supply Chain Solutions. UPS Logistics provides routing, scheduling, and dispatching systems for businesses with private fleets and wholesale distribution.20 The company claims to have over one thousand clients that use its services daily.

pages: 470 words: 144,455

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

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

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.