My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
March 8th, 2012, 09: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!
geliot is offline  
 
March 11th, 2012, 01: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  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
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 09:54 AM
GCD algorithm Bogauss Number Theory 14 March 1st, 2012 04:23 PM
Prime Numbers Sum Algorithm Question kokozko Number Theory 1 November 30th, 2011 08:53 AM
196-Algorithm skainstein Number Theory 6 September 15th, 2009 05:39 PM
What algorithm mmx64 Algebra 0 July 2nd, 2008 12:23 AM





Copyright © 2018 My Math Forum. All rights reserved.