is this NP-Hard?
in [General Programming]
|
From: Talha Lateef on 27 Apr 2010 15:48 On Apr 27, 2:58 pm, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Talha Lateef <talha...(a)gmail.com> writes: > > I want to solve a problem in  which i have been given a set of > > integers S and a Result R i need to find expression that equals result > > R i can use multiply, divide, addition and subtraction or concatenate > > number to create larger numbers my questions > > > what is the name of this problem? > > is this NP-Hard? > > Here is a simple algorithm to solve it: > > cond >   S = {}  ==> there is no solution >   S = {0} ==> if R = 0 then >           the solution is 0 >         else >           there is no solution >   else S={x}US' with xâ 0 >      Let's take x, and /, and apply x/x = 1 -> a >      Let's take x, and /, and apply x/x = 1 -> b >      Now, while a < R do >          let's take a, and b, and +, and appluy a+b â> a >      The solution is therefore R = x/x + x/x + x/x + ... + x/x > > Perhaps you want to revise your problem statement? > > -- > __Pascal Bourguignon__http://www.informatimago.com ok here is an example, S={3,2,1} R=4 so i need to find all combination which equals to R, for eg 3+2-1=4 numbers should be used in same order. thanks
From: Pascal J. Bourguignon on 28 Apr 2010 01:41 Talha Lateef <talhal82(a)gmail.com> writes: > On Apr 27, 2:58 pm, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: >> Talha Lateef <talha...(a)gmail.com> writes: >> > I want to solve a problem in  which i have been given a set of >> > integers S and a Result R i need to find expression that equals result >> > R i can use multiply, divide, addition and subtraction or concatenate >> > number to create larger numbers my questions >> >> > what is the name of this problem? >> > is this NP-Hard? >> >> Here is a simple algorithm to solve it: >> >> cond >>   S = {}  ==> there is no solution >>   S = {0} ==> if R = 0 then >>           the solution is 0 >>         else >>           there is no solution >>   else S={x}US' with xâ 0 >>      Let's take x, and /, and apply x/x = 1 -> a >>      Let's take x, and /, and apply x/x = 1 -> b >>      Now, while a < R do >>          let's take a, and b, and +, and appluy a+b â> a >>      The solution is therefore R = x/x + x/x + x/x + ... + x/x >> >> Perhaps you want to revise your problem statement? >> >> -- >> __Pascal Bourguignon__http://www.informatimago.com > > ok here is an example, S={3,2,1} R=4 so i need to find all combination > which equals to R, > for eg > 3+2-1=4 Then if you have |S| numbers in your sequence, you will need to build |{*,/,+,-,.}|^(|S|-1) combinations. This is clearly polynomial. -- __Pascal Bourguignon__
From: Kai-Uwe Bux on 2 May 2010 14:08 Pascal J. Bourguignon wrote: > Talha Lateef <talhal82(a)gmail.com> writes: > >> On Apr 27, 2:58 pm, p...(a)informatimago.com (Pascal J. Bourguignon) >> wrote: >>> Talha Lateef <talha...(a)gmail.com> writes: >>> > I want to solve a problem in which i have been given a set of >>> > integers S and a Result R i need to find expression that equals result >>> > R i can use multiply, divide, addition and subtraction or concatenate >>> > number to create larger numbers my questions >>> >>> > what is the name of this problem? >>> > is this NP-Hard? >>> >>> Here is a simple algorithm to solve it: >>> >>> cond >>> S = {} ==> there is no solution >>> S = {0} ==> if R = 0 then >>> the solution is 0 >>> else >>> there is no solution >>> else S={x}US' with x?0 >>> Let's take x, and /, and apply x/x = 1 -> a >>> Let's take x, and /, and apply x/x = 1 -> b >>> Now, while a < R do >>> let's take a, and b, and +, and appluy a+b ?> a >>> The solution is therefore R = x/x + x/x + x/x + ... + x/x >>> >>> Perhaps you want to revise your problem statement? >>> >>> -- >>> __Pascal Bourguignon__http://www.informatimago.com >> >> ok here is an example, S={3,2,1} R=4 so i need to find all combination >> which equals to R, >> for eg >> 3+2-1=4 > > Then if you have |S| numbers in your sequence, you will need to build > |{*,/,+,-,.}|^(|S|-1) combinations. This is clearly polynomial. Huh? It is clearly exponential in |S|. Since the set S is part of the input, the algorithm has exponential complexity. Best Kai-Uwe Bux
From: Pascal J. Bourguignon on 2 May 2010 16:37 Kai-Uwe Bux <jkherciueh(a)gmx.net> writes: > Pascal J. Bourguignon wrote: > >> Talha Lateef <talhal82(a)gmail.com> writes: >> >>> On Apr 27, 2:58 pm, p...(a)informatimago.com (Pascal J. Bourguignon) >>> wrote: >>>> Talha Lateef <talha...(a)gmail.com> writes: >>>> > I want to solve a problem in which i have been given a set of >>>> > integers S and a Result R i need to find expression that equals result >>>> > R i can use multiply, divide, addition and subtraction or concatenate >>>> > number to create larger numbers my questions >>>> >>>> > what is the name of this problem? >>>> > is this NP-Hard? >>>> >>>> Here is a simple algorithm to solve it: >>>> >>>> cond >>>> S = {} ==> there is no solution >>>> S = {0} ==> if R = 0 then >>>> the solution is 0 >>>> else >>>> there is no solution >>>> else S={x}US' with x?0 >>>> Let's take x, and /, and apply x/x = 1 -> a >>>> Let's take x, and /, and apply x/x = 1 -> b >>>> Now, while a < R do >>>> let's take a, and b, and +, and appluy a+b ?> a >>>> The solution is therefore R = x/x + x/x + x/x + ... + x/x >>>> >>>> Perhaps you want to revise your problem statement? >>>> >>>> -- >>>> __Pascal Bourguignon__http://www.informatimago.com >>> >>> ok here is an example, S={3,2,1} R=4 so i need to find all combination >>> which equals to R, >>> for eg >>> 3+2-1=4 >> >> Then if you have |S| numbers in your sequence, you will need to build >> |{*,/,+,-,.}|^(|S|-1) combinations. This is clearly polynomial. > > Huh? It is clearly exponential in |S|. Since the set S is part of the input, > the algorithm has exponential complexity. Oops! Right, I forgot S was the input. -- __Pascal Bourguignon__ http://www.informatimago.com/
From: Talha Lateef on 3 May 2010 05:29 I am thinking of creating a tree with temp Result in each node, each node has five childs {+,-,*,/,.}, if temp result of a node is greater than my Result then i will stop calculating that branch.
First
|
Prev
|
Next
|
Last
Pages: 1 2 3 Prev: Young girls showing off their bodies on personal webcams Next: Style (was Re: on goto) |