Knapsack Problem(mathematics) The problem, given a set of integers {A1, A2, …, An} and a target integer B, of determining whether a subset of the Ai can be selected without repetition so that their sum is the target B.
(Wikipedia) The knapsack problem is a problem in combinatorial optimization. It derives its name from the maximization problem of choosing possible essentials that can fit into one bag (of maximum weight) to be carried on a trip. A similar problem very often appears in business, combinatorics, complexity theory, cryptography and applied mathematics. Given a set of items, each with a cost and a value, then 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 decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the cost C?"
A simple knapsack implementation with recursion. Source: http://codebus.googlepages.com/knapsack
No comments:
Post a Comment