You have a pile of numbers and you want to know if any sub-group of numbers in the pile sum to some target. This is tricky to do by hand with a small group and nearly impossible to do with anything larger.
Given a set of numbers
267 961 1153 1000 1922 493 1598 869 1766 1246
is there any sub-group that sums to 5842?
Trying to do this by hand is a waste of time.
Make sure all submodules get pulled upon initial cloning.
git clone --recurse-submodules https://github.com/fuvvy/mfsum
Check that the required packages are installed.
autotools autotools-dev automake autoconf libtool gcc
Re-build the build environment after cloning the repository.
autoreconf --force --install
./configure
make
sudo make install
This program may benefit from more agressive optimization. You can control this when invoking the configure script.
./configure CFLAGS=-O3
mfsum only accepts positive integer input. It accepts input from either the command line or via standard input. The program requires three pieces of information in order to run.
- target value
- trim value
- list of numbers
The target value and the list need no explanation but the trim number does. It should be a number between 0 and 1 and providing this parameter will tell the program to find a approximate solution. Fore example, if you use 0.40, the program will find a sum that is within 40% of the target. Using this feature is advisable when the input set is very large. The trim value allows the program to drastically reduce running times since it is a polynomial time algorithm while the exact mode uses a exponential algorithm. Entering a 0 for the trim value envokes the exact sum mode.
mfsum 5842 0 267 961 1153 1000 1922 493 1598 869 1766 1246
5842 = 869 + 961 + 1000 + 1246 + 1766
The following example will find a solution that is within 10% of the target.
mfsum 5842 0.1 267 961 1153 1000 1922 493 1598 869 1766 1246
5802 = 961 + 1153 + 1766 + 1922
Invoking the program with a dash as its only argument instructs the program to wait for standard input. In this mode, the arguments must be provided line-by-line. The first and second lines must contain the target and trim values, respectively. The rest of the lines should contain the set. This makes it easy to provide larger automated inputs to mfsum. The input can be provided with a file as with this example.
File input.txt
5009813684
0
212153178
1427863024
1366863723
2027395864
2129420246
1017464478
640366018
1243516659
729987169
1039115050
607438639
265725058
2008186886
1121354568
1316780152
Running
mfsum - < input.txt
265725058
607438639
640366018
1366863723
2129420246
If the program is terminating with the error "Unable to allocate X bytes" and you are giving the program a large set of numbers, then the system could be running out of memory. It may be necessary to increase the memory limits enforced by the operating system. This can accomplished with the ulimit command.
| ulimit -c unlimited | turn on corefiles with unlimited size |
| ulimit -n unlimited | allows an unlimited number of open file descriptors |
| ulimit -d unlimited | sets the user data limit to unlimited |
| ulimit -f unlimited | sets the file limit to unlimited |
| ulimit -a | display the current ulimit settings |
Running ulimit -d unlimited sould take care of the problem until you
run out of physical memory and start swapping like crazy.
mfsum : A Subset Sum Solver Copyright 2018 Mike Fusaro
This file is part of mfsum.
mfsum is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
mfsum is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with mfsum. If not, see http://www.gnu.org/licenses/.