•
•
•
•
What is DaniWeb IT Discussion Community?
You're currently browsing the Computer Science and Software Design section within the Software Development category of DaniWeb, a massive community of 425,893 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 1,982 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.
Please support our Computer Science and Software Design advertiser: Programming Forums
Views: 532 | Replies: 2
 |
•
•
Join Date: Jun 2008
Posts: 75
Reputation: 
Rep Power: 1
Solved Threads: 3
Junior Poster in Training
I guess there is a "standard" algorithm for problems of this type.. the template would look like this:
given the integer n and n numbers, find the smallest sum you can get by adding the numbers like this:
n1+n2+n1+n2+n3+n1+n2+n3+n4...
the obvious way for me was to do some math on it and get the following;
for n = 5
you get
(n-1)(N1+N2)+(n-2)N3+(n-3)N4+(n-4)N5
so... from this i just thought sorting the array would do...
but it doesn't seem to be the right way... help!!!
given the integer n and n numbers, find the smallest sum you can get by adding the numbers like this:
n1+n2+n1+n2+n3+n1+n2+n3+n4...
the obvious way for me was to do some math on it and get the following;
for n = 5
you get
(n-1)(N1+N2)+(n-2)N3+(n-3)N4+(n-4)N5
so... from this i just thought sorting the array would do...
but it doesn't seem to be the right way... help!!!
Last edited by gregorynoob : Jul 7th, 2008 at 8:16 am.
•
•
Join Date: Oct 2007
Location: Cambridge, MA
Posts: 269
Reputation:
Rep Power: 2
Solved Threads: 22
Posting Whiz in Training
Your problem is the same as finding the smallest contiguous subsequence sum in the sequence
[n1, n1 + n2, n1 + n2 + n3, n1 + n2 + n3 + n4, ...].
Transform your sequence into this form and then solve the problem I described.
Come to think of it, solving the problem I described may involve doing the same transformation one more time.
[n1, n1 + n2, n1 + n2 + n3, n1 + n2 + n3 + n4, ...].
Transform your sequence into this form and then solve the problem I described.
Come to think of it, solving the problem I described may involve doing the same transformation one more time.
•
•
Join Date: Aug 2008
Posts: 1
Reputation:
Rep Power: 0
Solved Threads: 0
Newbie Poster
Its very interesting I like your thinking I appreciate you.Really I like your attitude.How will you get this type of knowledge.
Last edited by Ancient Dragon : Aug 4th, 2008 at 6:40 pm. Reason: sniped false signature
|
•
•
•
•
•
•
•
•
DaniWeb Computer Science and Software Design Marketplace
•
•
•
•
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
Linear Mode
- Pointers (archived tutorial) (C++)
- Need help to do an algorithm in C++ (C++)
- hi what was the impotance of algorithm in making program (C)
- Boolean Algebra (C++)
- C++, help!!!!!!! (C++)
- Combinations(N choose R) ? (C)
- Pointers (C++)
- Graphics In Pixel: Part II (C++)
Other Threads in the Computer Science and Software Design Forum
- Previous Thread: Discuss this scientific approach with solid comments.
- Next Thread: process and thread
