Dynamic Programming is a problem solving technique that solves a problem by dividing it into its subproblems. When the subproblems are similar that is they share the same property as the original problem and also they are dependent. It is normally used for optimizing a specific problem and follows the principle of optimality which states that for an optimal sequence of decisions, each sub-sequence must also be optimal.
List of possible parent DP problems with the possible least number of their variations(mentioned in square brackets). (source: google)
0-1 Knapsack[6]
Unbounded Knapsack[5]
Fibonacci[7]
Longest Common Subsequence[15]
Longest Increasing Subsequenc[10]
Kadane's Algorith[6]
Matrix Chain Multiplication[7]
DP on Trees[7]
DP on Grid[14]
Others(less common)[5]
so there are atleast 83 types of DP problems. There are possibly more which i dont know at this point.
Anyways, I will be studying and blogging about each of these porblems and their varations..
Nowdays I'm studying recursion, dynamic programming, solved some problems on it. There's this particular problem I was studying on, its called the knapsack problem.
I had so much trouble solving some knapsack problems, some were easy, some were clear to me but i couldnt solve them, later found that those problems were not of the same type even though they sound similar and i was constantly trying to tackle them with the same method.. Failed doing so. So I thought there must be some general types of knapsack problems. I did some googling and found that there are atleast six types of knapsack problems.
Knapsack problem is a name to a family optimization problems that have the following general theme: You are given a knapsack with a maximum weight/ capacity, and you have to select a subset of some given items such that a profit sum is maximium, without exceeding the capacity of the knapsack.
Further learnt that knapsack problem is a NP-hard problem. NP is a complexity class of computational problems and NP hard is the hardest among all the NP problems. Sounds scary right?, I think that explains why most DP problems have so small constraints. The easiest method to solve this problems is Dynamic Programming , which solves these problems in pseudo polynomial time.
Types of Knapsack problems;
0/1 knapsack problem : most basic type, given a knapsack with a maximum weight, and you have to select a subset of some given items such that a profit sum is maximized without exceeding the capacity of the knapsack.
Number partitioning : Partition a set S containing N integers, into two sets S1 and S2, so that |sum(L1) - sum(L2)| is minimized. This problem is perhaps even more general than the 0/1 knapsack problem and is one of the six basic NP-hard problems.
Bounded Knapsack : Instead of N items, you are given M types of items, each type having a bounded quantity.
Unbounded Knapsack : You have an unbounded quantity of each item type, instead of a bounded quantity.
Multiple Knapsack problem: same as the 0/1 knapsack problem but you are given multiple knapsacks of different sizes. The capacity constraint must be met for all of the knapsacks.
Box-packing problem : Also called as The Bin-packing problem. You have some number of equally sized bins. You need to pack the items into bins so that the number of bins used is as small as possible.
Each of this problem have different variations too. For example the 0/1 knapsack problem covers the following problems:
(i) Subset sum problem
(ii) Equal sum partion
(iii) Count of subset
(iv) Minimum subset sum
(v) Target sum
and lot more...
I understand knapsack problem much better now. And I'm confident and excited to solve newer variations of Knapsack problem or atleast similar problems just for fun. Will be posting about the problems with solutions.
Problem Statement: Given a set of items, each with a "weight" and a "value", determine the number of each item to include in a collection/knapsack, so that -> "the total weight is less than or equal to a given limit" and "the total value is as large as possible"
Explanation:
The value and the weight/cost of each item is given in the arrays val[] and wt[] respectively.
The nth item has value val[n] and weight wt[n]; The total capacity of knapsack is W
The solution is simple. Let dp[n][w] be the optimal value for the first n items with total value w. Now the next task would be to define dp[n][w] in terms of smaller subproblems, in terms of some recursive formula.
Consider the case in which the weight/ cost of the item is greater than the total capacity of knapsack.(i.e. w[n] > Total ) Since the current item exceeds the capacity of the knapsack, all we can do here is to ignore the item move to next item in the array.
Now, if the weight of the item is less than or equals to the total capacity of the knapsack, we'll have two choices:
we can either choose the item or not and move to next item. since we want maximum profit so we will have to go with the choice which gives us more profit.
If we choose the item, then we will have to decrease the capacity of knapsack by the weight of the current item.
If we don't choose the item then we will continue to next item with capacity of knapsack unchanged.
The first case is DP[n,w]= DP[n−1, w]. if wt[n] > W, meaning the n'th item weighs more then are target weight so it cannot be added even if the knapsack is empty.
The second case is the decision case, DP[n, W] = MAX( DP[n−1, W ], DP[n−1, W−wt[ n-1 ] ]+val[n-1] ) it means that either we don't add Item n to our set, in which case our best so far is DP[n−1,W], or we do add it, in which case we only have W−wt[n] weight remaining to be filled with items 1 to n-1 and our total value is DP[n−1,W−wt[n-1] ]+val[n-1], which is our recursive value plus the value of the new Item.
Algorithm (Iterative) :
# Given: val[n] --value array, wt[n] -- weight/cost array, W -- capacity of bag/knapsack;
(I) Initialize the first row and the first column of DP[][] array with zeros.
(II) Iterate through DP[][] array.
(III) For each DP[i][j] :
if j <= W then DP[I][j] = max( val[i-1] + DP[i-1][j-wt[i-1] , DP[i-1][j] );
else DP[I][j] = DP[i-1][j];
(IV) return DP[n][W];
As a final year student I'm required to do one project in mathematics, which is what I have always wanted to do! To make it more interesting, I have decided to write about this project here as a blog post.
The topic for my project is "computational number theory ", more specifically on primality tests and integer factorization algorithms.
Why I chose this topic?
I have interests in both mathematics and computer science and I had this in mind for some time to do some concrete work in both the fields. Also nowadays I'm studying algorithms, so I thought it a good idea to choose my project related to algorithms.
In my first year in college I read a book on number theory:
Elementary Number Theory by David Burton
It's an amazing book, especially the part of the theory of congruence, Chinese remainder theorem and continued fractions. I had developed some interest in number theory after reading that book.
So when it comes to project, honestly I couldn't think of anything else but Number Theory in which i already have good knowledge and experience.
Exactly what my project is about?
Prime numbers and Primality tests and Integer Factorization, which is one of the most important topics in number theory, will be the main focus of my project. The subject of primality of a number has been the focus of many scientific studies and several different theories has been developed for many years. Based on these theorems, primality of large numbers has been investigated. There are also computer algorithms to test primality of large numbers. I will be discussing different methods, algorithms to check primality and to factor large integers. I will also discuss about the best and worst cases for such algorithms, try to compare them and explain which algorithm is best in what condition. The Best method/algorithm will determined by comparing the test results with different methods/algorithms.
Apart from primality and Integer Factorization I will be giving an Introduction to some of the named primes such as Mersenne primes, Gaussian primes, irregular primes etc.
"Don't let anything stir you off the path you have drawn for yourself! Forge ahead in the end! Stick to it! Make yourself proud! Be everything you can be!"
while you're alive, you need a reason for your existence. Being unable to find one is the same as being dead.
when you give up your dreams and everythinng else, they're gone!
still complaining huh?
..!!!!!!!listen to yourself whining and complaining like some sorry little victim. you can whimper all day for all I care, youre nothing but a coward !!!!!!!....
....remember one thing , once you questioned your own belief, its over!
