Dynamic Programming

A place for implementation of greedy algorithms

Features

  • To see all the available functions in a module, you can just type help() with the module name as argument. For example,
>>> from pygorithm import greedy_algorithm
>>> help(greedy_algorithm)
    Help on package pygorithm.dynamic_programming in pygorithm:

    NAME
    pygorithm.dynamic_programming - Collection for dynamic programming algorithms

    PACKAGE CONTENTS
    binary_knapsack
    lis

    DATA
    __all__ = ['binary_knapsack', 'lis']

Binary (0/1) Knapsack

  • Functions and their uses

Author: Omkar Pathak Created At: 25th August 2017

pygorithm.dynamic_programming.binary_knapsack.knapsack(w, value, weight)[source]

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.

Parameters:
  • w – maximum weight capacity
  • value – an array of values of items in the knapsack
  • weight – an array of weights of items in the knapsack
pygorithm.dynamic_programming.binary_knapsack.get_code()[source]

returns the code for the knapsack function

Longest Increasing Subsequence

  • Functions and their uses

Author: Omkar Pathak Created At: 25th August 2017

pygorithm.dynamic_programming.lis.longest_increasing_subsequence(_list)[source]

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for [10, 22, 9, 33, 21, 50, 41, 60, 80] is 6 and LIS is [10, 22, 33, 50, 60, 80].

Parameters:_list – an array of elements
Returns:returns a tuple of maximum length of lis and an array of the elements of lis
pygorithm.dynamic_programming.lis.get_code()[source]

returns the code for the longest_increasing_subsequence function