subset_sum_brute

subset_sum_brute, an Octave code which uses brute force to solve the subset sum problem, to find a subset of a set of integers which has a given sum.

We are given a collection of (21) weights and a target value (24639098). We seek a combination of the weights which adds up to the target value.

The function subset_sum_brute() simply considers every possible subset of the weights, determines its sum, and compares that to the target value. The first case in which the target value is matched is returned as the solution.

This program, which solves the problem serially, is primarily intended to be a starting point for a parallel programming approach.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

subset_sum_brute is available in a C version and a C++ version and a Fortran90 version and a MATLAB version and an Octave version and a Python version.

Related Data and Programs:

subset_sum_brute_test

subset_sum, an Octave code which seeks solutions of the subset sum problem.

Reference:

• Silvano Martello, Paolo Toth,
  Knapsack Problems: Algorithms and Computer Implementations,
  Wiley, 1990,
  ISBN: 0-471-92420-2,
  LC: QA267.7.M37.

Source Code:

• i4_to_binary_digits.m returns the binary digits of an I4.
• subset_sum_brute.m, seeks a solution of the subset sum problem by exhaustive search.