Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse Newsgroups: comp.programming Subject: Re: Looking for simple brute force solution Date: Thu, 04 Jan 2018 02:29:30 +0000 Organization: A noiseless patient Spider Lines: 34 Message-ID: <87shbm8igl.fsf@bsb.me.uk> References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: reader02.eternal-september.org; posting-host="d91270aa90bb7038a06ebe75f0537788"; logging-data="22715"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19necP45tbBBebhZuG7CYI9xPNidqGwP5U=" Cancel-Lock: sha1:SBfbZz868uqh98H5WzktQyieMBg= sha1:1FD+kutKlQRgadk/9cec6TAHa3U= X-BSB-Auth: 1.8f7114c2b56e1b16a90d.20180104022930GMT.87shbm8igl.fsf@bsb.me.uk Xref: csiph.com comp.programming:8251 root writes: > 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. -- Ben.