dynamic_programming.knapsack

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Note that only the integer weights 0-1 knapsack problem is solvable using dynamic programming.

Attributes

val

Functions

_construct_solution(dp, wt, i, j, optimal_set)

Recursively reconstructs one of the optimal subsets given

knapsack(w, wt, val, n)

knapsack_with_example_solution(w, wt, val)

Solves the integer weights knapsack problem returns one of

mf_knapsack(i, wt, val, j)

This code involves the concept of memory functions. Here we solve the subproblems

Module Contents

dynamic_programming.knapsack._construct_solution(dp: list, wt: list, i: int, j: int, optimal_set: set)

Recursively reconstructs one of the optimal subsets given a filled DP table and the vector of weights

Parameters

dp: list of list, the table of a solved integer weight dynamic programming problem

wt: list or tuple, the vector of weights of the items i: int, the index of the item under consideration j: int, the current possible maximum weight optimal_set: set, the optimal subset so far. This gets modified by the function.

Returns

None

dynamic_programming.knapsack.knapsack(w, wt, val, n)
dynamic_programming.knapsack.knapsack_with_example_solution(w: int, wt: list, val: list)

Solves the integer weights knapsack problem returns one of the several possible optimal subsets.

Parameters

W: int, the total maximum weight for the given knapsack problem. wt: list, the vector of weights for all items where wt[i] is the weight of the i-th item. val: list, the vector of values for all items where val[i] is the value of the i-th item

Returns

optimal_val: float, the optimal value for the given knapsack problem example_optional_set: set, the indices of one of the optimal subsets which gave rise to the optimal value.

Examples

>>> knapsack_with_example_solution(10, [1, 3, 5, 2], [10, 20, 100, 22])
(142, {2, 3, 4})
>>> knapsack_with_example_solution(6, [4, 3, 2, 3], [3, 2, 4, 4])
(8, {3, 4})
>>> knapsack_with_example_solution(6, [4, 3, 2, 3], [3, 2, 4])
Traceback (most recent call last):
    ...
ValueError: The number of weights must be the same as the number of values.
But got 4 weights and 3 values
dynamic_programming.knapsack.mf_knapsack(i, wt, val, j)

This code involves the concept of memory functions. Here we solve the subproblems which are needed unlike the below example F is a 2D array with -1s filled up

dynamic_programming.knapsack.val = [3, 2, 4, 4]