C++ || Knapsack Problem Using Exhaustive Search

Print Friendly

The following is another homework assignment which was presented in an Algorithm Engineering class. Using a custom timer class, the following is a program which reduces the problem of selecting which Debian Linux packages to include on installation media, to the classical knapsack problem. This program implements an exhaustive search algorithm for this problem, and displays its performance running time to the screen.

NOTE: Looking for the Dynamic Programming version to this problem? Click here!

==== 1. OVERVIEW ====

Debian is a well-established GNU/Linux distribution. Ubuntu Linux, arguably the most popular Linux distribution, is based on Debian. Debian software is organized into packages. Each package corresponds to a software component, such as the GCC compiler or Firefox web browser. There are packages not only for the software that comprises the operating system, but also end-user applications. Nearly every piece of noteworthy open source software has a corresponding package. There are currently over 29,000 Debian source code packages available.

This wide selection of packages is mostly a good thing. However it poses a problem for creating installation media – the floppy disks, CDs, DVDs, or flash drive images that administrators use to install the operating system. If a user wants to install a package that is missing from their installation media they need to download it over the internet, so it is beneficial to include as many packages as possible. It is impractical to include every package on those media, so the Debian project needs to select a small subset of important packages to include.

Another part of Debian is the Popularity Contest, or popcon:

The Popularity Contest tries to measure the popularity of each Debian package. Users may elect to participate, in which case the list of their installed packages is transmitted back to Debian. These lists are tallied as votes. So, thanks to popcon, we can get a vote tally for each package.

==== 2. THE PROBLEM ====

This program solves the following problem:

Input: A list of Debian packages, each with a size (in kilobytes) and number of votes, both of which are integers; and an integer W representing the capacity of the install media (in kilobytes).

Output: The set of packages with total size ≤ W , such that the total number of package votes is maximized.

In terms of the knapsack problem, the Debian package votes correspond to knapsack values, and our Debian package sizes correspond to knapsack weights.

==== 3. THE INPUT ====

The following file (knapsack_packages.txt) contains the name, size, and votes for approximately 36,000 binary Debian packages that are currently available on the amd64 platform, and have popcon information.

The file obeys the following format:

[ number of packages ]
[ name 0 ] [ space ] [ votes 0 ] [ space ] [ size 0 ] [ newline ]
[ name 1 ] [ space ] [ votes 1 ] [ space ] [ size 1 ] [ newline ]
[ name 2 ] [ space ] [ votes 2 ] [ space ] [ size 2 ] [ newline ]

The packages are arranged within the file in sorted order, from the largest number of votes to the smallest.

==== 4. FLOW OF CONTROL ====

A test harness program is created which executes the above function and measures the elapsed time of the code corresponding to the algorithm in question. The test program will perform the following steps:

1. Load the "knapsack_packages.txt" file into memory.
2. Input size "n" and weight "W" as variables.
3. Execute the exhaustive search knapsack algorithm. The output of this algorithm should be the best combination sequence of packages.
4. Print the solution. A solution is the best sequence of packages, displaying the name of the package, the votes, and the size of each package, as well as the total votes and total size of the entire solution.

A knapsack problem instances is created of varying input sizes “n” by using the first “n” entries in the file knapsack_packages.txt. In other words, to create a problem instance with n = 100, only use the first 100 packages listed in the file as input.

==== 5. TEST HARNESS ====

Note: This program uses a custom Timer class (Timer.h). To obtain code for that class, click here.

“Project2.h” is listed below.

==== 6. THE ALGORITHMS – “include Project2.h” ====

The highlighted lines are sections of interest to look out for.

NOTE: Looking for the Dynamic Programming version to this problem? Click here!

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Note: Dont forget to include the input file!

The following is sample output:

n = 24, W = 65536

-- Exhaustive Search Solution --

debianutils 90 128329
libgcc1 46 128327
dpkg 2672 128294
perl-base 1969 127369
debconf 168 121503
grep 595 121426
gzip 142 121346
login 980 121332
coreutils 6505 121240
bash 1673 121229
sed 261 121220
findutils 805 121173
lsb-base 26 121121
sysv-rc 80 121092
sysvinit-utils 116 121078
base-files 65 121072
initscripts 93 121037
util-linux 846 121022
mount 272 120961
libselinux1 109 120918
cron 120 120872
base-passwd 49 120856
apt 1356 120826
tzdata 488 120813

Total Size = 19526 -- Total Votes = 2934456

It took 19140 clicks (19.14 seconds)

Leave a Reply