knapsack_01_brute, a C code which uses brute force to solve small versions of the 0/1 knapsack problem, in which a knapsack of limited weight capacity is to be packed as full as possible, selecting items from a set of varying weights;
This code uses a simple brute force or exhaustive search method, which is guaranteed to get the optimal solution, but which is not efficient for large values of N.
The information on this web page is distributed under the MIT license.
knapsack_01_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.
change_dynamic, a C code which considers the change making problem, in which a given sum is to be formed using coins of various denominations.
closest_pair_brute, a C code which uses brute force to solve a 2D version of the closest pair problem, which identifies the closest pair of points in a given collection.
combo, a C code which includes many combinatorial routines.
knapsack, a dataset directory which contains test data for the knapsack problem; we consider n items of given value and weight, and a knapsack with a weight limit. We wish to select items to store in the knapsack which maximize the total value.
knapsack_rational, a C code which solves the rational knapsack problem, in which a knapsack of limited weight capacity is filled with profitable items. This variation of the 0/1 knapsack problem allows a fractional part of an item to be included in the knapsack. The result is an upper bound on the maximum possible profit for the 0/1 knapsack problem.
matrix_chain_brute, a C code which finds the cost of the most efficient ordering to use when multiplying a sequence of matrices, using brute force.
partition_brute, a C code which uses a brute force method to find solutions of the partition problem, in which a set of integers must be split into two subsets with equal sum.
satisfy_brute, a C code which uses brute force to find all assignments of values to a set of logical variables which make a complicated logical statement true.
subset, a C code which enumerates, generates, ranks and unranks combinatorial objects including combinations, partitions, subsets, index sets, and trees.
subset_sum_brute, a C 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.
tsp_brute, a C code which reads a file of city-to-city distances and solves the traveling salesperson problem, using brute force.