``````
// enum - full enumeration of knapsack solutions
// (C) Joshua Knowles

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

FILE *fp;  // file pointer for reading the input files
int Capacity;     // capacity of the knapsack (total weight that can be stored)
int Nitems;    // number of items available
int *item_weights;  // vector of item weights
int *item_values;  // vector of item profits or values
int *temp_indexes;  // list of temporary item indexes for sorting items by value/weight
int QUIET=0; // this can be set to 1 to suppress output

extern void print_instance();
extern void sort_by_ratio();
extern int check_evaluate_and_print_sol(int *sol,  int *total_value, int *total_weight);
void enumerate();
int next_binary(int *str, int Nitems);

int main(int argc, char *argv[])
{
print_instance();
enumerate();
return(0);
}

void enumerate()
{
// Do an exhaustive search (aka enumeration) of all possible ways to pack
// the knapsack.
// This is achieved by creating every binary solution vector of length Nitems.
// For each solution vector, its value and weight is calculated.

int i;  // item index
int solution[Nitems+1];   // (binary) solution vector representing items packed
int best_solution[Nitems+1];  // (binary) solution vector for best solution found
int best_value; // total value packed in the best solution
double j=0;
int total_value, total_weight; // total value and total weight of current knapsack solution
int infeasible;  // 0 means feasible; -1 means infeasible (violates the capacity constraint)

// set the knapsack initially empty
for(i=1;i<=Nitems;i++)
{
solution[i]=0;
}
QUIET=1;
best_value=0;

while(!(next_binary(&solution[1], Nitems)))
{

/* ADD CODE IN HERE TO KEEP TRACK OF FRACTION OF ENUMERATION DONE */

// calculates the value and weight and feasibility:
infeasible=check_evaluate_and_print_sol(solution, &total_value, &total_weight);
/* ADD CODE IN HERE TO KEEP TRACK OF BEST SOLUTION FOUND*/

}
/* ADD CODE TO PRINT OUT BEST SOLUTION */

}

int next_binary(int *str, int Nitems)
{
// Called with a binary string of length Nitems, this
// function adds "1" to the string, e.g. 0001 would turn to 0010.
// If the string overflows, then the function returns 1, else it returns 0.
int i=Nitems-1;
while(i>=0)
{
if(str[i]==1)
{
str[i]=0;
i--;
}
else
{
str[i]=1;
break;
}
}
if(i==-1)
{
return(1);
}
else
{
return(0);
}
}
``````

A genuine UoM lab.