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.

more here:

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&section=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&section=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&section=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)

]