[algogeeks] Integer partition problem - DP
Given an integer how many number of ways u can partition the number? e.g. 3 can be written as 3,1+2,1+1+1 and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2 So for 3 -- 3 for 4 --5. The order of the elements in the partition does not matter. So how to calculate the number of ways to partition the given number? Can someone give idea on how to write the recurrence relation for the problem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Integer partition problem - DP
Problem is similar to coin change problem(i.e given an array of coins denomination , Find number of ways to create N Rupees).So given input K...fill up array from 1 to K.and use this array and a input to coin change problem On Sat, Mar 1, 2014 at 9:55 PM, kumar raja rajkumar.cs...@gmail.com wrote: Given an integer how many number of ways u can partition the number? e.g. 3 can be written as 3,1+2,1+1+1 and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2 So for 3 -- 3 for 4 --5. The order of the elements in the partition does not matter. So how to calculate the number of ways to partition the given number? Can someone give idea on how to write the recurrence relation for the problem? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Integer partition problem - DP
Let us assume you have sum S. The possible numbers it is made up are { 1,
2, .., S }.
Now, for every number belonging to the set, you have two options.
1. Subtract currently chosen number from the given set to sum.
2. Choose next number.
The state will be defined as (num, sum), where num is the number you are
using and sum is current sum.
Recurrence will be,
f (num, sum) = f (num - 1, sum) + f (num, sum - num)
f (num, 0) = 1
f (0, sum) = 0
The translation to code is fairly obvious, which reduces to O (N^2) time
and O (N^2) space dp.
// Code.
int memo [55][505];
int
solve (int num, int sum) {
// f (num, sum) = f (num - 1, sum) + f (num, sum - num)
if (sum == 0) return 1;
if (sum 0 || num = 0) return 0;
if (memo [num][sum] != -1) return memo [num][sum];
return memo [num][sum] = solve (num - 1, sum) + solve (num, sum - num);
}
int
main () {
memset (memo, -1, sizeof (memo));
for (int i = 0; i = 10; i++) printf (%d %d\n, i, solve (i, i));
return 0;
}
Output:
0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
Assuming, order matter, [i.e. 1 + 2 != 2 + 1], it reduces to simple
take-it or leave-it knapsack. Though this is tangential to your question.
On Sat, Mar 1, 2014 at 9:55 PM, kumar raja rajkumar.cs...@gmail.com wrote:
Given an integer how many number of ways u can partition the number?
e.g. 3 can be written as 3,1+2,1+1+1
and 4 can be written as 4, 1+1+1+1,2+2,1+3,1+1+2
So for 3 -- 3
for 4 --5.
The order of the elements in the partition does not matter.
So how to calculate the number of ways to partition the given number?
Can someone give idea on how to write the recurrence relation
for the problem?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Why do I love the programming contests if I'm so bad at it?
I have been an programmer my whole life, and it is my passion. I have done many problems, I've helped a lot to other coders, and I've made contests online constest in topcoder, codeforces a lot of times. On top of all of this, I surround myself with other contesters as friends. Sadly, I recently did some thinking and learned that I am a bad programming contester. A very bad programming contester; I can't do a lot of DP problems, I can't remember the algorithms during the contests, I can't solve a lot of of the easy math problems, I can't think against the time very well, I can't solve the problems which had similar ideas to the problems that I solved already. I know what makes a good programming contester, and I've studied algorithm problems and maths for years, but for some reason, I just can't code to save my life, even though I love it with that life. My question to you all is this, even though I love to solve problems more than anything else in the world, should I just give up on it? I am not getting anything out of it, and there are no chances around me to learn anything and improve, so should I forget it and find a new passion? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
