This was part of a recursion assignment in Computer Science I taught by Dr. Cazalas at UCF.

Assignment Specification

You are working on an engineering project with other students and are in need of 2x4s (2 by 4’s) of various lengths. Thankfully, UCF has its very own “Depot” store: KnightsDepot…so you don’t have to drive far. Unfortunately, KnightsDepot only carries 2x4s in fixed lengths. So your team will have to purchase the 2x4s and then cut them as needed. Because of your tight college student budget, you want to buy the least number of 2x4s in order to cover the lengths requested by your team.

The recursive function you are designing will return the minimum number of 2x4s you need to purchase, in order to cover the lengths requested by your team. Example:

Array of 2x4 lengths requested by your team: { 6, 4, 3, 4, 1, 3 } Fixed length of 2x4s at KnightsDepot: 6 (so each purchased 2x4 has a length of 6) A possible arrangement of of 2x4s: { 6 } { 3, 3 } { 4, 1 } { 4 } Minimum number of 2x4s needed to purchase: 4

Approach to solving
-------------------
My initial thought to solve this was to use a "greedy" algorithm which simply makes the best possible choice for the next board so that no scrap is wasted.
This method of solving is certainly faster than the final solution, but it is possible for this method not to be the most efficient use of boards.
The correct solution was to permutate the order in which you bought the boards and do a simple in-order purchase and calculate if this order performed better than the previous.

``` c KnightsDepot.c
/*  precondition:   fin/fout are pointers to the input/output file
    postcondition:  calculates the minimum amount of boards needed for project
*/
void KnightsDepot(FILE *fin, FILE *fout) {

    //read in args
    int size, whole;
    fscanf(fin, "%d %d", &whole, &size);

    if (DEBUG) printf("Read in argument size: %d, whole: %d\n", size, whole);

    //need to DAM for board array
    int * boards = (int *) malloc(sizeof(int)*size);

    //read in boards
    int i;
    for (i=0; i < size; i++)
        fscanf(fin, "%d", &boards[i]);

    //begin solving
    if (DEBUG) printf("KnightsDepot:  \n");
    fprintf(fout, "KnightsDepot:  ");    

    //edgecase: if boards to be bought are zero then just print 0 and get out
    if (size == 0) { 
        fprintf(fout, "%d\n\n", 0);
        if (DEBUG) printf("\ntotal boards: %d\n\n", 0);
        return;
    }

    //for passing by reference into DepotPermuteAndCalc
    //setting value to -1 indicates no boards have been counted yet.
    int runningCount = -1;

    //recurse
    int total = DepotPermuteAndCalc(boards, size, 0, whole, &runningCount);

    fprintf(fout, "%d\n\n", total);
    if (DEBUG) printf("\ntotal boards: %d\n\n", total);

    //cleanup
    free(boards);

    return;
}


/*  precondition:   boards is the array of our board lengths of size size.  fixed is the range we are holding            
                    in place [0-fixed] while we permute. whole is the dimension of the boards at the store and
                    runningCount is a pointer which holds the value of the least amount of boards we purchased 
                    through all the permutations.
    postcondition:  returns the minimum number of boards needed for the project.
*/
int DepotPermuteAndCalc(int boards[], int size, int fixed, int whole, int *runningCount) {

    if (DEBUG) {
        printf("PermutateAndCalc() size:%d, fixed:%d, whole:%d, runningCount:%d\n", size, fixed, whole, *runningCount);
        int i;
        for (i=0; i<size; i++)
            printf("%d ", boards[i]);
        printf("\n");
    }

    //basecase 
    if (fixed == size) {
        //calculate number of boards needed for this permutation
        int count = DepotCalcBoards(boards, size-1, whole);

        //compare to past permuations or just set it to runningCount if this is first permutation (-1)
        if (*runningCount == -1 || count < *runningCount)
            *runningCount = count;
    }

    //permutate
    int i;
    for (i=fixed; i < size; i++) {

        swap(boards, fixed, i);
        DepotPermuteAndCalc(boards, size, fixed+1, whole, runningCount);
        swap(boards, fixed, i);
    }

    //return our lowest count
    return *runningCount;
}


/*  precondition:   boards is the array of our board lengths of size size.  whole is the dimension of the boards 
                    at the store.
    postcondition:  returns the number of boards needed doing a 'dumb' linear addition
*/
int DepotCalcBoards(int boards[], int size, int whole) {

    int i;
    int working = 0;

    //start at the end of the array and figure out how many boards we can get
    for(i=size; i >= 0; i--) {

        working += boards[i];

        //the boards divide evenly into the whole dimension
        if (working == whole) {

            //are we at the end of array?
            if (i == 0) return 1;

            //no so recurse
            else return 1 + DepotCalcBoards(boards, i-1, whole);
        }

        //we have to waste the rest of the board and recurse with current i as new size
        if (working > whole) return 1 + DepotCalcBoards(boards, i, whole);

    }

    //if we get this far then we have a stray cut that needs to be made
    return 1;
}


/*  precondition:   a is the position that will be put into b and vice-versa
    postcondition:  switches the values at index a and index b in the array
*/
void swap(int array[], int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
    return;
}
```