Knapsack

Implementation of the recursive depth-first search algorithm for the subset sum problem (a variation of the knapsack problem).

What is This

This program implements a solver for a knapsack variant where there is a multiset of integers to select a valid subset from, where a valid subset's sum is exactly equal to the target value.

In the case of multiple valid subsets, a subset with the least number of elements out of all valid subsets is found; and in the case of multiple valid subsets with the lowest number of elements, the subset with elements that are closest to each other are chosen.

Why Was This Made

For fun, to practice C programming, and to solve problems using recursion.

How It Works

1. The program checks if the set is sorted, and sorts it in ascending order (using iterative selection sort) if it is not. This is to ensure the valid subset that is found first will have the lowest possbile amount of elements out of all valid subsets.
2. The recursive function combs through all the possible subsets, choosing either to take or skip each element in the sorted set until it finds a valid subset. Each function call creates 2 new branches like a binary tree, and the elements have to summed to be compared to the target value, so the algorithm has a time complexity of O(2^n * n) (where n is the number of elements in the original set).
3. In every function call (except the root, when the subset would be empty at first), the sum of the elements in the subset are first compared to the target value. If the sum of the subset is equal to the target, a valid subset is found. When a valid subset is found or the function calls reach a 'leaf' of the tree (done going through a full path of selecting elements from the original set), the pointer to the subset (or to NULL, if invalid) is returned back up the tree until it reaches the root.
4. The binary tree first branches all the way down to the subset with 0 elements (skipping all elements), goes back 1 step to take the largest (last) element in the sorted set, and if that is not a valid subset, then goes back another step to walk down the other branch. It repeatedly goes back to try out new branches until it either finds a valid subset. If it goes back enough and reaches the root, it starts the same process all over again, but now with the smallest (first) element of the sorted set included in the subset.
5. Due to arrays having fixed size, a zero is used to denote the end of the subset if the subset is not the same as the original sorted set. This is so that garbage from the unused allocated array memory is not displayed when looping through the array to print out the numbers in the subset. For non-zero target values, an optimal subset should have no zeros as zeros contribute nothing to the sum, so zero is used to denote the end of subsets.
6. The first function call then returns the subset for the main program to print out on the terminal using a for-loop in another helper function located in knapsack.c.

Limitations

• For ease-of-use, this program is designed to only handle integer values, but it can be easily modified to allow more (such as floating-point and even characters).
• Since the recursive search function skips all elements first, one call is effectively always wasted for every run with a non-zero target value and non-empty-set solution.

Usage

Download the binary files here.

Then follow the examples below to run the program.

Linux Terminal

./[i686/x86_64]-redhat-linux [target] [set[0] set[1] ...]

Example

./x86_64-redhat-linux 42 1 -13 0 3 0 -1 4 2 8 9 10 24 36

Subset of the above command should be {8, 10, 24}.

Windows Command Line

.\[i686/x86_64]-windows.exe [target] [set[0] set[1] ...]

Example

.\x86_64-windows.exe 42 1 -13 0 3 0 -1 4 2 8 9 10 24 36

Subset of the above commands should be {8, 10, 24}.

Legend

• [i686/x86_64]: CPU architecture (32-bit / 64-bit)

• [target]: Value of subset's sum

• [set[0] set[1] ...]: Set of numbers seperated by spaces; set[0] is the first number in the set, set[1] is the second, etc

How to Compile

• There is a shell script build.sh included to automate the compiling process to produce binaries for both Linux and Windows platforms

Requirements

• Since it is a shell (.sh) script and not a batch (.bat / .cmd) script, you need to be running Linux
• glibc-devel.x86_64 has to be installed if you want to compile for 64-bit Linux
• glibc-devel.i686 has to be installed if you want to compile for 32-bit Linux
• mingw64-gcc has to be installed if you want to compile for 64-bit Windows
• mingw32-gcc has to be installed if you want to compile for 32-bit Windows