Hi,
I am looking for an algorithm that figures out which numbers from a
given set add up to another number. I am sure this has been done
before, but I have no idea how such a calculation is called, which
kind of limits my further searching.
An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
should calculate all possible combinations of these numbers that add
up to 10. Each number can be used more than one time or not at all.
possible solutions are:
10 x 1
5 x 2
3 x 2 + 4
1 + 4 + 5
2 + 3 + 5
1 + 2 + 3 + 4
etc.
In this case it's pretty easy to do it on paper, but when the numbers
become larger (>1000) it would be nice to have a program to do this.
Any suggestions how to do this and/or where to start looking ?
thanks,
- Koen. 5 4209
Koen wrote: Hi,
I am looking for an algorithm that figures out which numbers from a given set add up to another number. I am sure this has been done before, but I have no idea how such a calculation is called, which kind of limits my further searching.
Are you talking addition or multiplication or both?
The above paragraph talks about addition, but the solutions show
multiplication. An example. The set contains the numbers 1-2-3-4-5. Now the algorithm should calculate all possible combinations of these numbers that add up to 10. Each number can be used more than one time or not at all.
Again, you state addition, but the example shows multiplication.
What is exact definition of the problem? possible solutions are:
10 x 1 5 x 2 3 x 2 + 4 1 + 4 + 5 2 + 3 + 5 1 + 2 + 3 + 4
etc.
Let us see, the first solution is invalid according to the given rules.
"10 x 1" is not a solution because the number "10" is not a member of
the set [1,2,3,4,5].
According to your problem definition, the first three solutions:
10 x 1
5 x 2
3 x 2 + 4
are all invalid solutions since they involve multiplication.
In this case it's pretty easy to do it on paper, but when the numbers become larger (>1000) it would be nice to have a program to do this.
As I've been thinking about this problem, it is not easy.
The given solution set does not match the problem definition.
The number of solutions involving mulitiplication is not a finitie
set, given the rule that any number may be used more than once and
the rule of multiplication by 1.
Addition, on the other hand, is a finite set, as long a zero is not
within the set. The rule of addition with zero provides an infinite
quantity of terms for a solution.
Any suggestions how to do this and/or where to start looking ?
Yes, get your problem definition correct before proceeding.
Start looking at:
combinatorics
recursion
linked list
stack
Identity Theorum for Multiplication
Identity Theorum for Addition
Programming loop constructs.
Greatest Common Factor (GCF)
Lowest Common Denominator (LCD)
logarithms (sp?)
Series expansion
If this is homework, slap your instructor and say "bad assignment"
then ramble off the Identity Theorums and say this is a never
ending waste of computer cycles (the same as an infinite loop).
thanks,
- Koen.
I would first start out with either multiplication or addition and
get them working. The multiplication with addition adds more
complexity to the function (as well as combinations).
Since "Each number can be used more than one time",
how does one know when to stop?
For example,
5 x 2
5 x 2 x 1
5 x 2 x 1 x 1
5 x 2 x 1 x 1 x 1 ...
--
Thomas Matthews
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.l earn.c-c++ faq: http://www.raos.demon.uk/acllc-c++/faq.html
"Koen" <kv******@earth link.net> wrote in message
news:dd******** *************** **@posting.goog le.com...
| I am looking for an algorithm that figures out which numbers from a
| given set add up to another number. I am sure this has been done
| before, but I have no idea how such a calculation is called, which
| kind of limits my further searching.
|
| An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
| should calculate all possible combinations of these numbers that add
| up to 10. Each number can be used more than one time or not at all.
.....
| In this case it's pretty easy to do it on paper, but when the numbers
| become larger (>1000) it would be nice to have a program to do this.
.....
| Any suggestions how to do this and/or where to start looking ?
Not really a question about C... but anyway:
A somewhat similar classic is the "knapsack problem".
A classic approach to solve this type of thing is "Dynamic programming".
(NB: this is not about dynamic code generation, 'programming' is
to be taken in a mathematical sense).
Googling for these terms should take you in the right direction.
I hope this helps,
Ivan
-- http://www.post1.com/~ivec
Thomas Matthews wrote: Koen wrote:
Hi,
I am looking for an algorithm that figures out which numbers from a given set add up to another number. I am sure this has been done before, but I have no idea how such a calculation is called, which kind of limits my further searching. Are you talking addition or multiplication or both? The above paragraph talks about addition, but the solutions show multiplication.
An example. The set contains the numbers 1-2-3-4-5. Now the algorithm should calculate all possible combinations of these numbers that add up to 10. Each number can be used more than one time or not at all.
Again, you state addition, but the example shows multiplication. What is exact definition of the problem?
possible solutions are:
10 x 1 5 x 2 3 x 2 + 4 1 + 4 + 5 2 + 3 + 5 1 + 2 + 3 + 4
etc.
Let us see, the first solution is invalid according to the given rules. "10 x 1" is not a solution because the number "10" is not a member of the set [1,2,3,4,5].
According to your problem definition, the first three solutions: 10 x 1 5 x 2 3 x 2 + 4 are all invalid solutions since they involve multiplication.
In this case it's pretty easy to do it on paper, but when the numbers become larger (>1000) it would be nice to have a program to do this.
As I've been thinking about this problem, it is not easy. The given solution set does not match the problem definition. The number of solutions involving mulitiplication is not a finitie set, given the rule that any number may be used more than once and the rule of multiplication by 1.
Addition, on the other hand, is a finite set, as long a zero is not within the set. The rule of addition with zero provides an infinite quantity of terms for a solution.
Any suggestions how to do this and/or where to start looking ? Yes, get your problem definition correct before proceeding. Start looking at: combinatorics recursion linked list stack Identity Theorum for Multiplication Identity Theorum for Addition Programming loop constructs. Greatest Common Factor (GCF) Lowest Common Denominator (LCD) logarithms (sp?) Series expansion
If this is homework, slap your instructor and say "bad assignment" then ramble off the Identity Theorums and say this is a never ending waste of computer cycles (the same as an infinite loop).
thanks,
- Koen.
I would first start out with either multiplication or addition and get them working. The multiplication with addition adds more complexity to the function (as well as combinations).
Since "Each number can be used more than one time", how does one know when to stop? For example, 5 x 2 5 x 2 x 1 5 x 2 x 1 x 1 5 x 2 x 1 x 1 x 1 ...
-- Thomas Matthews C Faq: http://www.eskimo.com/~scs/c-faq/top.html alt.comp.lang.l earn.c-c++ faq: http://www.raos.demon.uk/acllc-c++/faq.html
Aw, come on!
It seems obvious that the original posting
10x1
is just a shorthand for saying "1+1+1+1+1+1+1+ 1+1+1"
and was not meant to say that multiplication was part of the deal.
--
Fred L. Kleinschmidt
Associate Technical Fellow
Boeing Common User Interface Services
In article <3f********@new s.swissonline.c h>,
"Ivan Vecerina" <iv**@myrealbox .com> wrote: A somewhat similar classic is the "knapsack problem". A classic approach to solve this type of thing is "Dynamic programming". (NB: this is not about dynamic code generation, 'programming' is to be taken in a mathematical sense).
Googling for these terms should take you in the right direction.
I hope this helps, Ivan
Thanks Ivan for a grown-up response ;) I will look into the knapsack
problem.
- Koen.
In article <Nj************ **********@news svr28.news.prod igy.com>,
Thomas Matthews <Th************ **********@sbcg lobal.net> wrote: Are you talking addition or multiplication or both? The above paragraph talks about addition, but the solutions show multiplication.
If this is homework, slap your instructor and say "bad assignment" then ramble off the Identity Theorums and say this is a never ending waste of computer cycles (the same as an infinite loop).
Sorry Thomas, I don't understand your replies. I am glad another reader
gave a more mature reply and pointed me in the correct direction (my
problem is similar to the 'knapsack problem').
have a nice day,
- Koen. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Michael Peuser |
last post by:
Hi,
I should like to make a distribution (using Tkinter), with standard DLLs
removed.
pythonXX.dll is no problem.
tcl und tk, which make the mass of mega bytes, cannot be removed because
_tkinter.pyd seems to expect them in the same directory
(Question 1) Is there a configration or path setting in py2exe/distutils I
|
by: Tan Thuan Seah |
last post by:
Hi all,
I am looking for a way to generate a random number given the variance of a
gaussian distribution(or normal distribution). The mean is 0 but the
variance will be a user input. Does C++ have any of this sort of generator
available? Or must I use some transformation to get a random number from a
standardised normal distribution and map it to my distribution? Any link and
references are welcome.
Thuan Seah
|
by: aegis |
last post by:
is there any trickery that can be done
with rand() so that it generates a uniformly
distributed sequence?
Suppose that I want any thing in the range
m..n (inclusive) to be generated such that
I never have a recurrence of a number.
I could build a table I suppose as I call
rand and any number in that table already
|
by: ben |
last post by:
hello,
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths. i don't really
understand what is expected, or really what the question means. could
anyone explain what the question's after please?
any help much appreciated.
thanks, ben.
Prove an upper bound on the number of machine instructions required to
|
by: Raven |
last post by:
Hi to all, I need to calculate the hpergeometric distribution:
choose(r, x) * choose(b, n-x)
p(x; r,b,n) = -----------------------------
choose(r+b, n)
choose(r,x) is the binomial coefficient
I use the factorial to calculate the above formula but since I am using
large numbers, the result of choose(a,b) (ie: the binomial coefficient)
| |
by: Ulterior |
last post by:
Hi, everyone,
I have a simple problem, which bothers me for some while. I will try
to explain it -
There is some string, whith different letters in it. Is it possible to
analyse this string and the
reffer to it knowing that it has some certain letters in it using only
some integer value?
|
by: Verbal Kint |
last post by:
DEAR ALL,
I just have a very short question. In the FAQ list question 13.20 the
following text is mentioned:
"These methods all generate numbers with mean 0 and standard deviation
1. (To adjust to some other distribution, multiply by the standard
deviation and add the mean.)"
Could you please let me know, which number I have to multiply with the
standard deviation?
|
by: cr4kb0y |
last post by:
hello all:
I have to program a function which can produce a Poisson
Distribution number,I have no idea about it,
anyone who can give some suggestions? thanks!
|
by: Alex |
last post by:
Hi everybody,
I wonder if it is possible in python to produce random numbers
according to a user defined distribution?
Unfortunately the random module does not contain the distribution I
need :-(
Many thanks
axel
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |