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