The smallest project on my list, this is a single C++ file born out of a single bonus question on an assignment I received in a discrete optimization course:
It turns out that this problem can be solved by hand with a little bit of guess-and-check and some luck, or with some nested loops in Python (which is what I did), which ended up a bit disappointing, since it should require some thought to solve. So I decided to act as if I hadn’t already solved it and implemented a well-optimized solver using dynamic programming.
#include <iostream>
#include <time.h>
#include <limits.h>
long long int BETA = 89716837;
const int NUM_VAR = 6;
int a[NUM_VAR] = {12228, 36679, 36682, 48908, 61139, 73365};
int* initializeValueArray() {
int* value = new int[BETA+1];
cout << "Array Allocated" << endl;
for (int j = 0; j < a[0]; j++) {
value[j]= 0;
}
cout << "First few thousand array entries initialized" << endl;
for (int j = a[0]; j <= BETA; j++) {
// Uncomment for progress indicators. Adds quite a bit of time.
//if (j%1000000 == 0) {
// cout << j/1000000 << endl;
//}
for (int i = 0; i < NUM_VAR; i++) {
if (j - a[i] < 0) {
continue;
}
int newvalue = value[j - a[i]] + a[i];
if (newvalue > value[j]) {
value[j] = newvalue;
}
}
}
return value;
}
int* findPacking(int* value) {
int* x = new int[NUM_VAR];
for (int i = 0; i < NUM_VAR; i++) {
x[i] = 0;
}
if (value[BETA] != BETA) {
for (int i = 0; i < NUM_VAR; i++) {
x[i] = -1;
}
return x;
}
int j = BETA;
while (j >= a[0]) {
for (int i = 0; i < NUM_VAR; i++) {
if (j - a[i] < 0) {
continue;
}
if (value[j] == value[j-a[i]] + a[i]) {
x[i]++;
j -= a[i];
}
}
}
return x;
}
int main() {
clock_t t;
t = clock();
int* value = initializeValueArray();
cout << "89704609: " << value[89704609] << endl;
int count = 0;
for (int i = 0; i <= BETA; i++) {
if (i != value[i]) {
count++;
}
}
cout << "Number of infeasible indices: " << count << endl;
cout << "Number of feasible indices: " << BETA - count << endl;
t = clock() - t;
cout << "Done Initialization. Took " << float(t)/CLOCKS_PER_SEC << " seconds." << endl;
t = clock() - t;
int* soln = findPacking(value);
if (soln[0] == -1) {
cout << "No solution found." << endl;
} else {
cout << "Solution Found. Took " << float(t)/CLOCKS_PER_SEC << " seconds." << endl;
}
for (int i = 0; i < NUM_VAR; i++) {
cout << soln[i] << endl;
}
delete value;
delete soln;
}
This is a good example of a problem that is definitely “hard” in the complexity theory sense, but in practice, we can solve many “medium”-sized instances with a smart implementation.