Re: need a function for sums of subsets

• To: mathgroup at smc.vnet.net
• Subject: [mg33040] Re: [mg33001] need a function for sums of subsets
• From: Ken Levasseur <Kenneth_Levasseur at uml.edu>
• Date: Wed, 27 Feb 2002 00:47:56 -0500 (EST)
• References: <200202250631.BAA09782@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Mark:

You didn't say how you would order the subsets, so "first" isn't
defined.   Also, since finding any list is essentially the knapsack
problem it would seem to me that efficiency will be a problem.

Ken Levasseur
Math. Sciences.
UMass Lowell

Mark Ganson wrote:

> Hello,
>
> I need a function that will find the first subset of a list that will
> sum up to a given value.
>
> For example, if I have a list of rationals:
>
> myrationals = {1/2, 1/3, 1/4, 1/8, 3/10, 12/79, 13/38}
>
> I would like a function that will return the first subset of
> myrationals that sums up to a given parameter.
>
> We can call the function "findsum".  It would work like so:
>
> In: findsum[myrationals, 3/4]
> Out: {1/2, 1/4}
>
> It would be nice also, but not essential, to be able to use another
> list as the second parameter and have the function return a list of
> lists.
>
> Example:
>
> In: findsum[myrationals, {3/4, 3/8}]
> Out: {{1/2, 1/4}, {1/4, 1/8}}
>
> I need something really fast and memory efficient because my lists
> tend to be quite large (up to 100 elements).
>
> Many thanks,
>
> Mark Ganson

```

• Prev by Date: Re: Animation in one frame?
• Next by Date: Re: GraphicsArray
• Previous by thread: Re: need a function for sums of subsets
• Next by thread: Re: need a function for sums of subsets