Re: Looking for simple brute force solution

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Looking for simple brute force solution
Date	2018-01-04 02:29 +0000
Organization	A noiseless patient Spider
Message-ID	<87shbm8igl.fsf@bsb.me.uk> (permalink)
References	<p2jobe$48s$1@news.albasani.net>

Show all headers | View raw

root <NoEMail@home.org> writes:
<snip>
> I have a similar problem with a list of numbers, say
> 20 numbers. Each number can either be ignored, added
> to a running sum, or subtracted from the running sum.
> The problem is to find the combination such that the
> running sum is closest to a given value.
>
> Since there are 3 options for each number there are
> 3^N possible cases for a list of N numbers. I tried
> thinking about expanding the number of options to
> 4 so that two bits of a counter running from 0 to
> 4^N could be used but this runs up the number of
> tests very rapidly. 3^10  is about 59,000 tries,
> 4^10 is over a million.

You can just count up to 3^N.  Call the count i.  For each number in the
set you use i%3 to determine if you add, subtract or ignore.  For the
next number you set i = i/3 and repeat.  In effect you are pulling out
the base-3 digits of i.  (I'm using % to mean remainder and / for
integer division.)

> I am willing to suffer through a brute force method
> because I don't have to solve a large number of these
> problems, but I would like a solution that I could
> use for a list of 20 or 30 numbers.

That's a lot of sums to calculate.  If you can do a million a second,
N=30 would take over 6.6 years.  N=20 is more manageable but even then I
think you might have to take some shortcuts.

<snip>
-- 
Ben.

Thread

Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-03 23:18 +0000
  Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 16:49 -0800
    Re: Looking for simple brute force solution fir <profesor.fir@gmail.com> - 2018-01-03 17:11 -0800
      Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 10:14 +0000
        Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:52 -0500
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:46 +0000
            Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 12:37 -0500
  Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-03 21:28 -0500
    Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:42 +0000
      Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 10:16 -0500
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 17:26 +0000
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:19 +0000
  Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 02:29 +0000
    Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 09:55 +0000
      Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 14:29 +0000
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 16:55 +0000
          Re: Looking for simple brute force solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-04 20:36 +0000
      Re: Looking for simple brute force solution Robert Wessel <robertwessel2@yahoo.com> - 2018-01-04 12:03 -0600
        Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:28 +0000
          Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 21:50 +0000
            Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-04 23:06 +0000
            Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-04 21:35 -0500
              Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 05:59 +0000
                Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-05 16:48 +0000
                Re: Looking for simple brute force solution Richard Damon <Richard@Damon-Family.org> - 2018-01-06 08:50 -0500
                Re: Looking for simple brute force solution root <NoEMail@home.org> - 2018-01-06 16:47 +0000

csiph-web