Looking for simple brute force solution

From	root <NoEMail@home.org>
Newsgroups	comp.programming
Subject	Looking for simple brute force solution
Date	2018-01-03 23:18 +0000
Organization	Linux Advocacy
Message-ID	<p2jobe$48s$1@news.albasani.net> (permalink)

Show all headers | View raw

Suppose you have a problem each of N items is to be included
or excluded and any combination of these items yields some
figure of merit. A brute force solution to determine the
best combination is to realize there are 2^N possible
combinations and you can run a counter from 0 to 2^N and
examine the bits of each counter to determine whether the
corresponding item is included (1) or excluded (0).

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.

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.

Background:
This problem arises from trying to read entries in
financial statements in which some entries are totals
of other entries but the meaning of the entries is
not well defined. It is as in an income statement
in which some entries are sources of income, some
are expenses, and some are intermediate sums of
other entries.

I hope I have described the problem sufficiently well
to spark a solution in your mind. If so, I thank
you for sharing that spark.

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

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