Re: Notebook for low density subset sum?
- To: mathgroup at smc.vnet.net
- Subject: [mg40729] Re: [mg40528] Notebook for low density subset sum?
- From: Kirk Reinholtz <kirk.reinholtz at jpl.nasa.gov>
- Date: Tue, 15 Apr 2003 03:59:00 -0400 (EDT)
- References: <200304090533.BAA08379@smc.vnet.net> <3E943199.289F8DAC@wolfram.com>
- Sender: owner-wri-mathgroup at wolfram.com
Last week I posted this question. The actual problem I was attempting
to solve was this:
"Given the set of reciprocal squares of positive integers, find a subset
of that set that sums to exactly 1/2."
I was told only that there were less than one hundred terms in the
answer.
After trying many search algorithms, I finally came up with the
following backtracking approach, thanks
to a chain of thoughts started by Daniel Lichtblau of WRI. Thought you
all might be interested. First
I converted it to a subset sum problem, then solved that with a
backtracking search and some pruning.
I was manually iteratively deepening the search when I hit the answer,
using only a few tens of CPU seconds
on my 2GHz wintel machine.
vtmp =Table[1/n^2,{n,2,21+19}];
len=Length@vtmp;
lc = LCM@@Denominator@vtmp;
v = lc*vtmp;
tottbl = Plus@@v-FoldList[#1+#2&,0,v];
s = lc*1/2;
b = Table[0,{len}];
feasibleQ[i_,tot_] := tot <= s <= tot+tottbl[[i]];
solutionQ[i_,tot_] := tot \[Equal] s;
try[i_?(#1<=len&),tot_] :=With[{rtot = tot+v[[i]]},
b[[i]] = 1;
solutionQ[i,rtot] && Throw[b];
If[feasibleQ[i+1,rtot],
try[i+1,rtot]];
b[[i]] = 0;try[i+1,tot];
];
try[i_,tot_];
Catch[try[1,0]] // Timing
- References:
- Notebook for low density subset sum?
- From: Kirk Reinholtz <kirk.reinholtz@jpl.nasa.gov>
- Notebook for low density subset sum?