# Approximation Algorithm Programs
This directory demonstrates solutions to various NP-hard and NP-complete problems, written in __C__.

## Knapsack Problem (FPTAS)

### Instructions to run:
1. In the `/knapsack` directory, enter "make" into the command line to create the executable.
2. Type "./knapsack" and then press <kbd>ENTER</kbd>.
3. Type each line of data, delimited by a space, and press <kbd>ENTER</kbd> after each line. Data should be entered as follows:
    1. The first line should contain the __*profits*__ for each item, delimited by a space.
    2. The second line should contain the __*sizes*__ for each item, delimited by a space. Line 2 should contain the same number of items as Line 1.
    3. The third line should contain the __*capacity*__ of the knapsack as a single integer.
    4. Finally, the fourth line should contain the value for __*epsilon*__, a decimal greater than 0 and less than 1 that sets the *approximation factor* for the algorithm.
4. Once the fourth line is entered and <kbd>ENTER</kbd> is pressed, the program will begin.

>### EXAMPLE:
>For a problem where 5 items have 
>__*profits*__ of 4, 20, 12, 12, and 2, and 
>__*sizes*__ of 2, 7, 4, 4, and 1, respectively,
>the knapsack has a __*capacity*__ of 9,
>and __*epsilon*__ is 0.5, the four lines inputted would be:
>1. `4 20 12 12 2`
>2. `2 7 4 4 1`
>3. `9`
>4. `0.5`


## Set Cover Problem (Primal-Dual Schema)

### Instruction to run:
1. In the `/setcover` directory, enter "make" into the command line to create the executable.
2. Type "./setcover" and then press <kbd>ENTER</kbd>.
3. Type each line of data, delimited by a space, and press <kbd>ENTER</kbd> after each line. One line should be entered for each set in the problem, starting with the __*cost*__ of the set, a space, and then each __*element*__ in the set, delimited by a space.
4. Once each set's data has been entered into a line, type "0" in the final line and press <kdb>ENTER</kbd> to begin the program.

>### EXAMPLE:
>For a problem with 
>__*sets*__ {a,b}, {a,c,d}, {b,d,e}, and {a,b,e}, and
>__*costs*__ of 2, 4, 3, and 3, respectively, the lines inputted would be:
>1. `2 a b`
>2. `4 a c d`
>3. `3 b d e`
>4. `3 a b e`
>5. `0`