Dynamic programming
Contents
About
Dynamic programming is a way of breaking large problems into smaller problems and minimizing the amount of re-calculation needed by the "memorization" of answers to the smaller problems. This page is still under construction, but the links below give some good examples of how dynamic programming works.
Steps
Solving dynamic programming problems typically involves three steps:
- Characterize the structure and/or a recursive definition for an optimal solution
- Initialize the structure
- Compute the value of an optimal solution in a bottom-up fashion
- Construct an optimal solution from the computed information.
Knapsack Problem
The Knapsack problem is a conical dynamic programming question. The question is:
Given weights and values(profits) of N items, put these items in a knapsack of max capacity W to get the maximum total value(profit) in the knapsack.
The solution is explained fairly well here: 0/1 Knapsack Problem solved using Iterative and Dynamic Programming. Each item is either selected or not selected (binary).... and to try every combination of items would be O(N^2).. so instead of that the solution is to break it into it's smallest part.
Say we have 4 items:
- shirt (1kg) = $2.00
- shoe (3kg) = $2.40
- pants (2kg) = $1.40
- trophy (5kg) = $1.50
... If our capacity is 1kg and we only have a shirt, the answer is obvious ... there is only one choice.... you expand from there.
Links
- Dynamic Programming - Wikipedia
- Dynamic Programming Tutorial for Needleman/Wunsch "global alignment" - goes through an example of the Needleman/Wunsch technique
- A Tutorial on Dynamic Programming - a nice list of problems by Michael Trick including the "knapsack problem" and many others
