algorithms.dynamic_programming

Knapsack

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit.

optimal_weight(capacity, weights)

Function calculate optimal_weight for rucksack from given list of weights

Parameters:

• capacity – max capacity of rucksak
• weights – list of weights

Returns:

Max possible weight that meet <= max capacity

Examples

>>> optimal_weight(165, [23, 31, 29, 44, 53, 38, 63, 85, 89, 82])
165