My Math Forum Algorithm question

 Computer Science Computer Science Forum

 March 8th, 2012, 08:05 AM #1 Newbie   Joined: Apr 2011 Posts: 7 Thanks: 0 Algorithm question Hi all, I'm trying to find an algorithm - no code, just words on paper - and I'm running into a wall here. The input is an array A[1..n] of n different integers, and an integer, b The question is in how many ways can b be written as the sum of elements of the array when any element A[i] can be used in the sum at most once. I'm looking for a solution that runs at O(nb) time. It seems like a dynamic approach is the only way this is going to work, but I can't really think of a subproblem that I could break it up into; it doesn't seem like it should be too difficult, but I'm totally hitting a wall. (also, in case its not clear, i'm *pretty* sure the integers in the array increase by 1 each time, i.e. for n=4 we have A[1,2,3,4]). Thanks so much for any help/hints!
 March 11th, 2012, 12:59 PM #2 Senior Member   Joined: Feb 2012 Posts: 628 Thanks: 1 Re: Algorithm question If all of the integers are in sequence, you can check to see if b is greater than or equal to the sum of all of them. What you're going to need is a way of determining how many ways you can write an integer in the array as a sum of the others. I would start as follows: If b is equal to one of the numbers in the array, then you have already calculated how many ways you can write each integer as a sum of the others, so that is your answer. If b is larger than all of them, then start with the largest number and keep adding the next largest number until the sum is greater than or equal to b.

 Tags algorithm, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Bogauss Number Theory 15 March 19th, 2012 08:54 AM Bogauss Number Theory 14 March 1st, 2012 03:23 PM kokozko Number Theory 1 November 30th, 2011 07:53 AM skainstein Number Theory 6 September 15th, 2009 04:39 PM mmx64 Algebra 0 July 1st, 2008 11:23 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top