January 2017
Beginner to intermediate
280 pages
217h 11m
English
The knapsack problem involves the maximization or the minimization of a value, such as profits or costs. As in a linear programming problem, there are restrictions in a knapsack problem. Imagine a knapsack or pouch that can hold only a certain weight or volume. We can place different types of items in the knapsack. Our objective is to place items in the knapsack to maximize total value without breaking the knapsack because of too much weight or a similar restriction.
Many kinds of problems can be classified as knapsack problems. Choosing items to place in the cargo compartment of an airplane and how to best cut sheet metal are examples. The restriction can be volume, weight, or both. Some scheduling ...