My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum

LinkBack Thread Tools Display Modes
March 8th, 2012, 08:05 AM   #1
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!
geliot is offline  
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.
icemanfan is offline  

  My Math Forum > Science Forums > Computer Science

algorithm, question

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
GCD new algorithm? Bogauss Number Theory 15 March 19th, 2012 08:54 AM
GCD algorithm Bogauss Number Theory 14 March 1st, 2012 03:23 PM
Prime Numbers Sum Algorithm Question kokozko Number Theory 1 November 30th, 2011 07:53 AM
196-Algorithm skainstein Number Theory 6 September 15th, 2009 04:39 PM
What algorithm mmx64 Algebra 0 July 1st, 2008 11:23 PM

Copyright © 2019 My Math Forum. All rights reserved.