knapsack problem

Algorithms Unlocked
by Thomas H. Cormen
Published 15 Jan 2013

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. 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.

…

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.

…

It doesn’t matter which set we say that y t is in, so let’s say that it’s in S 0 . Now, we know that the integers in S 0 sum to y, which means that the integers in S 0 other than y t must sum to y .y t/, or t. Since y ´ C t cannot also be in S 0 , we know that all the other integers in S 0 came from R. Hence, there is a subset of R that sums to t. 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.

Applied Cryptography: Protocols, Algorithms, and Source Code in C
by Bruce Schneier
Published 10 Nov 1993

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.

…

In general, the time required to solve this problem seems to grow exponentially with the number of items in the pile. 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? If the list of weights is a superincreasing sequence, then the resulting knapsack problem is easy to solve. A superincreasing sequence is a sequence in which every term is greater than the sum of all the previous terms. For example, {1, 3, 6, 13, 27, 52} is a superincreasing sequence, but {1, 3, 4, 9, 15, 25} is not.

Life's Edge: The Search for What It Means to Be Alive
by Carl Zimmer
Published 9 Mar 2021

Now you must find the combination of items with the greatest value that is under a certain weight. Many businesses face practical versions of the Knapsack Problem. Airline companies want to figure out how to pack their planes so they can deliver the most valuable cargo using the least amount of fuel. Financial firms look for the best way to spread their funds across investments with different potential returns. There’s no simple equation to solve the Knapsack Problem, though. Researchers have filled books with strategies to get us close to the best solution. Slime molds may not be able to write books, but they can solve the Knapsack Problem. Audrey Dussutour, a scientist at Paul Sabatier University in Toulouse, France, and her colleagues brought their skill to light by translating the problem into the terms that matter to slime molds: food.

…

The slime molds built what looked remarkably like the American interstate highway system. They have mimicked Tokyo subways and Canada’s transportation network. It’s unsettling to mathematicians that slime molds can solve this kind of problem in a few days. It’s kept them busy for centuries. Another puzzle that has kept generations of mathematicians busy is known as the Knapsack Problem. Imagine you’re preparing for a hike, and you have to decide what to put in your knapsack. You can choose from a lot of different items that are more or less useful for the trip. But you also have to keep in mind the weight of your items, since you can’t pack an infinite number of them. You might tuck a deck of cards in your backpack so that you’d be able to pass the time on rainy mornings in the mountains playing poker.

…

See also genes and genetics Herzog, Carl, 90–92, 97, 99–101 hexuronic acid, 175 hibernation, 93–101 Hitler, Adolph, 177 HMS Beagle, 157 HMS Challenger, 152–54, 163–66 HMS Cyclops, 156, 160 HMS Lightning, 162 HMS Rattlesnake, 154–56, 156–57 Hoffman, Friedrich, 129 homeostasis, 93–101, 109, 124 hominins, 40–41 Hooker, Joseph, 217–18 hormones, 31, 58–60 Horowitz, Norman, 253, 254 hot springs, 216–17, 235, 236–38, 243 Hubbs, Carl, 213–14 Hubbs, Laura, 213–14 Hungary, 174, 176 Huxley, Thomas, 154–56, 157–58, 160–67, 219 hybrids, 213–14 hydrocarbons, 221, 236 hydrochloric acid, 73, 149 hydrogen sulfide, 216 Indian Institute of Technology Guwahati, 87 influenza, 206 information flows, 289–90 intelligence, 81–82, 88–89 International Committee on Taxonomy of Viruses, 210 International Space Station (ISS), 9–10, 242, 261 in vitro fertilization, 31–32 irritability, 139–43, 144–45, 158, 173 Jakosky, Bruce, 277–78 Jet Propulsion Laboratory (JPL), 250–55, 259, 260, 262 John of Naples, 21–22 Johnson Space Center, 255 Joseph II, Holy Roman Emperor, 143 Journal of the American Medical Association, 53 Joyce, Gerald, 199, 209 Jupiter, 260 Kasianowicz, John, 230 Kaufmann, Stuart, 283, 284–85, 286, 291 kelp, 5–6 kidneys, 52–53, 60, 70, 74 Knapsack Problem, 85–86 Koch, Christof, 33–34 Kolbe, Hermann, 150 Kompanichenko, Vladimir, 236 Lamarckian evolution, 270 Lavoisier, Antoine, 149 Lederberg, Joshua, 25, 34, 251, 254 Leduc, Stéphan, 265 Lee, Patrick, 27 legal standards of life and death, 25, 53–55, 55–62 “Legal Start of Life, The” (Washington Post), 25 Lenski, Richard, 115–16 Leonardo da Vinci, 280–81 Lewis, C.

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

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?

…

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.

Algorithms to Live By: The Computer Science of Human Decisions
by Brian Christian and Tom Griffiths
Published 4 Apr 2016

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.

…

“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.”

…

.; 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.

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

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.

…

“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.

Competing on Analytics: The New Science of Winning
by Thomas H. Davenport and Jeanne G. Harris
Published 6 Mar 2007

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.

Secrets and Lies: Digital Security in a Networked World
by Bruce Schneier
Published 1 Jan 2000

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.

Accelerando
by Stross, Charles
Published 22 Jan 2005

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.