|
|
| View previous topic :: View next topic |
| Author |
Message |
Haonus
Guest
|
 Posted: Tue May 22, 2007 11:01 am Post subject: A question,help me |
 |
|
Hey,guys!
choose SOME units from{7,9,14,17,18,25,28,34,36}
goal:The sum of the units you choosed is 100
tell me your great arithmetic,thankx |
|
| Back to top |
|
 |
| |
Ads |
Advertising
Sponsor
|
|
kundan
Guest
|
| Posted: Tue May 22, 2007 11:01 am Post subject: Re: A question,help me |
|
|
On May 22, 11:53 am, Haonus <kyli...@gmail.com> wrote:
| Quote: |
Hey,guys!
choose SOME units from{7,9,14,17,18,25,28,34,36}
goal:The sum of the units you choosed is 100
tell me your great arithmetic,thankx
|
7+9+14+34+36=100
I don't understand the purpose of the question.is it supposed to be
hard? |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Haonus
Guest
|
| Posted: Wed May 23, 2007 8:33 am Post subject: Re: A question,help me |
|
|
On May 22, 4:09 pm, kundan <kundan.it...@gmail.com> wrote:
| Quote: |
On May 22, 11:53 am,Haonus<kyli...@gmail.com> wrote:
Hey,guys!
choose SOME units from{7,9,14,17,18,25,28,34,36}
goal:The sum of the units you choosed is 100
tell me your great arithmetic,thankx
7+9+14+34+36=100
I don't understand the purpose of the question.is it supposed to be
hard?
|
My bad.The purpose is how many subsets,the sum is 100,could you find?
Just like 7,9,14,34,36 is a subset. I wanna know a good arithmetic to
compute every set. |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Gerry Myerson
Guest
|
| Posted: Wed May 23, 2007 8:47 am Post subject: Re: A question,help me |
|
|
In article <1179821391.405159.23640@y18g2000prd.googlegroups.com>,
kundan <kundan.itbhu@gmail.com> wrote:
| Quote: |
On May 22, 11:53 am, Haonus <kyli...@gmail.com> wrote:
Hey,guys!
choose SOME units from{7,9,14,17,18,25,28,34,36}
goal:The sum of the units you choosed is 100
tell me your great arithmetic,thankx
7+9+14+34+36=100
I don't understand the purpose of the question.is it supposed to be
hard?
|
It is a simple instance of what is believed to be, in general,
a very hard problem, known as the knapsack problem.
You could look it up.
--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email) |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
Haonus
Guest
|
| Posted: Fri May 25, 2007 11:01 am Post subject: Re: A question,help me |
|
|
On May 23, 10:29 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
| Quote: |
Gerry Myerson <g...@maths.mq.edi.ai.i2u4email> writes:
In article <1179821391.405159.23...@y18g2000prd.googlegroups.com>,
kundan <kundan.it...@gmail.com> wrote:
On May 22, 11:53 am,Haonus<kyli...@gmail.com> wrote:
Hey,guys!
choose SOME units from{7,9,14,17,18,25,28,34,36}
goal:The sum of the units you choosed is 100
tell me your great arithmetic,thankx
7+9+14+34+36=100
I don't understand the purpose of the question.is it supposed to be
hard?
It is a simple instance of what is believed to be, in general,
a very hard problem, known as the knapsack problem.
You could look it up.
That won't find all
? v=[7,9,14,17,18,25,28,34,36];p=1+O(x^101);for(i=1,#v,p*=(1+x^v[i]));polcoeff(p,100)
5
solutions.
The trivial algorithm to find all solutions is O(2^9)=512 steps.
However, you can meet-in-the-middle for O(2^5)+O(2^4)=48 slightly harder steps.
{7,9,14,17} can yield sums of S={0,7,9,14,16,17,21,23,24,26,30,31,33,38,40,47}
Stick these values, plus the combination that formed them, in a hash or a bitmap.
Looking at the power set of {18,25,28,34,36}, in no particular order
{} and all singletons can't make 100-n for any n in S, nor any pairs
less than 53.
18+36=54, 46 not in S
25+28=53, 47 in S => {7,9,14,17,25,28} is a solution
25+34=59, 41 not in S
25+36=61, 39 not in S
28+34=62, 38 in S => {7,14,17,28,34} is a solution
28+36=64, 36 not in S
34+36=70, 30 in S => {7,9,14,34,36} is a solution
etc.
(Done by hand, may have errors.)
Of course, that's still exponential, you just halved the exponent.
However, that technique is hot to trot long after the naive algorithm
explodes. I don't believe it can be bettered, deterministically.
Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.- Hide quoted text -
- Show quoted text -
|
Hi Phil
Thanks for your arithmetic.
why did you choose a subset{7,9,14,17}? I think you have compute the
MEAN of the set{7,9,14,17,18,25,28,34,36},am I right?
Hannus |
|
| Back to top |
|
|
| |
Ads |
Advertising
Sponsor
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
