dynamic_programming.knapsack
============================

.. py:module:: dynamic_programming.knapsack

.. autoapi-nested-parse::

   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
----------

.. autoapisummary::

   dynamic_programming.knapsack.val


Functions
---------

.. autoapisummary::

   dynamic_programming.knapsack._construct_solution
   dynamic_programming.knapsack.knapsack
   dynamic_programming.knapsack.knapsack_with_example_solution
   dynamic_programming.knapsack.mf_knapsack


Module Contents
---------------

.. py:function:: _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``


.. py:function:: knapsack(w, wt, val, n)

.. py:function:: 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


.. py:function:: 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 ``-1`` s filled up


.. py:data:: val
   :value: [3, 2, 4, 4]