Knapsack problem¶
Some Theory:
The knapsack problem or rucksack problem is a problem in combinatorial optimization.
Given a set of items, each with a weight and a value, 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 and the total value is as large as possible.
It derives its name from the problem faced by someone, who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Abstract module¶
Abstract helper module for check correct other solutions in tests Also define “Item” and “Knapsack” abstract types
-
class
knapsack_problem.ref_func.
Item
[source]¶ Atomic thing with his own characteristics
-
name:
Name of item
-
value:
Cost of item
-
weight:
Weight of item
Create new instance of Item(name, value, weight)
-
-
class
knapsack_problem.ref_func.
Knapsack
[source]¶ Knapsack characteristics
-
items:
one of Item above
-
weight_limit:
limit of Knapsack for items
Create new instance of Knapsack(items, weight_limit)
-
-
knapsack_problem.ref_func.
knapsack_standard_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → knapsack_problem.ref_func.Item[source]¶ Standard solution for knapsack problem in Python https://codereview.stackexchange.com/a/20581
Solutions module¶
Examples of python realization of solution for knapsack problem
-
knapsack_problem.funcs.
knapsack_1_standard_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → knapsack_problem.ref_func.Item[source]¶ https://codereview.stackexchange.com/a/20581
Solve the knapsack problem by finding the most valuable subsequence of items that weighs no more than weight_limit.
items must be a sequence of pairs (value, weight), where value is a number and weight is a non-negative integer.
weight_limit is a non-negative integer.
Return a pair whose first element is the sum of values in the most valuable subsequence, and whose second element is the subsequence.
-
knapsack_problem.funcs.
knapsack_2_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → knapsack_problem.ref_func.Item[source]¶ my own function, written thanks to the site: https://foxford.ru/wiki/informatika/algoritm-ukladki-ryukzaka
-
knapsack_problem.funcs.
knapsack_3_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → knapsack_problem.ref_func.Item[source]¶ Given a list of items with name, value and weight. Return the optimal value with total weight <= allowed weight and list of picked items. https://codereview.stackexchange.com/a/125386
-
knapsack_problem.funcs.
knapsack_4_bruteforce_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → Union[knapsack_problem.ref_func.Item, List[None]][source]¶ Brute force algorithm http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1&action=edit§ion=62
-
knapsack_problem.funcs.
knapsack_5_dynamic_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → knapsack_problem.ref_func.Item[source]¶ Dynamic programming solution http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1&action=edit§ion=63
-
knapsack_problem.funcs.
knapsack_6_recursive_dynamic_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → Tuple[knapsack_problem.ref_func.Item][source]¶ Recursive dynamic programming algorithm http://rosettacode.org/mw/index.php?title=Knapsack_problem/0-1&action=edit§ion=64
-
knapsack_problem.funcs.
knapsack_greedy_solution
(items: Tuple[knapsack_problem.ref_func.Item], weight_limit: int) → Iterator[T_co][source]¶ Return a list of items with the maximum value, subject to the constraint that their combined weight must not exceed max_weight. Implements the well-known “greedy approximation algorithm” for the knapsack problem (first described by George Dantzig in 1957). https://codereview.stackexchange.com/a/62871
Data describes¶
functions with “_static_” in name - correct proven examples of input output for knapsack problem So, for debugging funcs.py I used it for checking correct behavior, because output of “_static_” functions write in docstrings and we can compare strings with construction:
from operator import attrgetter
expected_result = data.__doc__.replace('\n', '').replace(' ', '')
result = sorted(func(*data()), key=attrgetter('name'))
result = str(result).replace(' ', '')
For all other tests i use random data with as many arguments as I need For output I use one of funcs, reference function, on which correct I am convinced It’s on ref_func.py But i still use it for other test for check other parameters, not only correctness
-
knapsack_problem.data.
create_dynamic_knapsacks
(*, start: int, end: int, step: int = 1) → Dict[str, Dict[str, Union[knapsack_problem.ref_func.Knapsack, Tuple[knapsack_problem.ref_func.Item]]]][source]¶ Dynamic create collections of Items
result = { knapsack_*weight_limit*: { 'input': Tuple[Item], # generated items 'output': Knapsack, # Knapsack answer by knapsack_standard_solution (for checking with other solutions) } }
-
knapsack_problem.data.
pack_up_static_knapsack_1
() → knapsack_problem.ref_func.Knapsack[source]¶ [
Item(name=’camera’, value=6, weight=1),
Item(name=’food’, value=9, weight=2),
Item(name=’water’, value=10, weight=3)
]
-
knapsack_problem.data.
pack_up_static_knapsack_2
() → knapsack_problem.ref_func.Knapsack[source]¶ [
Item(name=’book’, value=1, weight=1),
Item(name=’food’, value=2, weight=1),
Item(name=’jacket’, value=2, weight=2),
Item(name=’water’, value=6, weight=4)
]
-
knapsack_problem.data.
pack_up_static_knapsack_3
() → knapsack_problem.ref_func.Knapsack[source]¶ [
Item(name=’apple’, value=39, weight=40),
Item(name=’beer’, value=52, weight=10),
Item(name=’book’, value=30, weight=10),
Item(name=’camera’, value=32, weight=30),
Item(name=’t-shirt’, value=24, weight=15),
Item(name=’tin’, value=68, weight=45),
Item(name=’trousers’, value=48, weight=10),
Item(name=’umbrella’, value=73, weight=40),
Item(name=’water’, value=153, weight=200)
]