Subset Sum Problem

Problem Statement:   Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

1. For every element In the array, we have a choice of whether to select this item or not.
2. If the value of the element is strictly greater than the Sum, the element cannot be taken. But, if the value of the element is not greater than Sum, then we have two choices. we either choose the element or we don't choose the element. 
3. If we choose the element the Sum should be decrease by the value of the element. If we dont choose the element the Sum left unchanged. 
4. After this the nth array element is now processed. we move to next array element which    (n-1) the element with new Sum value. so now we have the new sub-porblem.
5. we do this recursively for every array element solving the subproblems  eventually  the      original problem is solved.


/*
Let our arr[n] be the given array and  DP[n][S], a boolean value, represent sif there exists a subset with sum S and n elements;
then, 
if( arr[n] <= S) --> DP[n][S] = DP[n-1][S-arr[n]] or DP[n-1][S];
else --> DP[n][S] = dp[n-1][S];

*/

In recursive (TOP-DOWN) approach our task is to divide the given problem in the further subproblems.


// Recursive Method.

//Iterative Method

Random thoughts and Jokes

[warning! Mathematical jokes ahead, you may get headache.]

1. Suppose there is no empty set. Then consider the set of all empty sets.
2. Top ten excuses for not doing homework:

• I accidentally divided by zero and my paper burst into flames.
• Isaac Newton's birthday.
• I could only get arbitrarily close to my textbook. I couldn't actually reach it.
• I have the proof, but there isn't room to write it in this margin.
• I was watching the World Series and got tied up trying to prove that it converged.
• I have a solar powered calculator and it was cloudy.
• I locked the paper in my trunk but a four-dimensional dog got in and ate it.
• I couldn't figure out whether i am the square of negative one or i is the square root of negative one.
• I took time out to snack on a doughnut and a cup of coffee.
• I spent the rest of the night trying to figure which one to dunk.
• I could have sworn I put the homework inside a Klein bottle, but this morning I couldn't find it.

3. The biggest lie of the century, “I have read and agree to the terms of …”

4. The difference between an introvert and extrovert mathematicians is: An introvert mathematician looks at his shoes while talking to you. An extrovert mathematician looks at your shoes.  LOL.

5. Math is the language God used to write the universe.

6. Biologists think they are biochemists,
Biochemists think they are Physical Chemists,
Physical Chemists think they are Physicists,
Physicists think they are Gods,
And God thinks he is a Mathematician.

7. Teacher: Now suppose the number of sheep is x...
Student: Yes sir, but what happens if the number of sheep is not x?

8. If I have seen farther than others, it is because I was standing on the shoulders of giants.
-- Isaac Newton

In the sciences, we are now uniquely privileged to sit side by side with the giants on whose shoulders we stand.
-- Gerald Holton

If I have not seen as far as others, it is because giants were standing on my shoulders.
-- Hal Abelson

Mathematicians stand on each other's shoulders.
-- Gauss

Mathematicians stand on each other's shoulders while computer scientists stand on each other's toes.
-- Richard Hamming

It has been said that physicists stand on one another's shoulders. If this is the case, then programmers stand on one another's toes, and software engineers dig each other's graves.
-- Unknown

9. "The problems for the exam will be similar to the discussed in the class. Of course, the numbers will be different. But not all of them. Pi will still be 3.14159... "


10.                                      A SLICE OF PI

 
                    ******************
                     3.14159265358979
                       1640628620899
                        23172535940
                         881097566
                          5432664
                           09171
                            036
                             5

11.
[This poem was written by John Saxon (an author of math textbooks)].

A Dozen, a Gross and a Score,
plus three times the square root of four,
divided by seven,
plus five times eleven,
equals nine squared and not a bit more.

In arctic and tropical climes,
the integers, addition, and times,
taken (mod p) will yield
a full finite field,
as p ranges over the primes.

A graduate student from Trinity
Computed the cube of infinity;
But it gave him the fidgets
To write down all those digits,
So he dropped math and took up divinity.

Chebychev said it and I'll say it again:
There's always a prime between n and 2n!

A conjecture both deep and profound
Is whether the circle is round;
In a paper by Erdo"s,
written in Kurdish,
A counterexample is found.

(Note: Erdo"s is pronounced "Air - dish")

There once was a number named pi
Who frequently liked to get high.
All he did every day
Was sit in his room and play
With his imaginary friend named i.

There once was a number named e
Who took way too much LSD.
She thought she was great.
But that fact we must debate;
We know she wasn't greater than 3.

There once was a log named Lynn
Whose life was devoted to sin.
She came from a tree
Whose base was shaped like an e.
She's the most natural log I've seen

Dynamic Programming

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)

1. 0-1 Knapsack[6]
2. Unbounded Knapsack[5]
3. Fibonacci[7]
4. Longest Common Subsequence[15]
5. Longest Increasing Subsequenc[10]
6. Kadane's Algorith[6]
7. Matrix Chain Multiplication[7]
8. DP on Trees[7]
9. DP on Grid[14]
10. 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..

Happy Coding!

Knapsack Problems

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;

1. 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.
2. 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.
3. Bounded Knapsack : Instead of N items, you are given M types of items, each type having a bounded quantity.
4. Unbounded Knapsack : You have an unbounded quantity of each item type, instead of a bounded quantity.
5. 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.
6. 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.

0/1 Knapsack: Algorithm, Explanation and Code;

0/1 Knapsack: Algorithm, Explanation and Code;

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

Sample Problem: https://www.spoj.com/problems/KNAPSACK/
Solution code: