December 2005 Problem 'scales' Analysis

The brute force approach tries every possible combination of weights, adds them up, and checks against the best current combination and the upper bound. For 40 weights, there are 2⁴⁰ sets - roughly 10¹², which is far too slow. The unusual property of the weights (that w[i+2] >= w[i+1] + w[i]) allows one to speed up the algorithm. If we write

w[3] - w[2] >= w[1]
w[4] - w[3] >= w[2]
            :
            :
w[i+2] - w[i+1] >= w[i]

• w[N-1] + w[N] <= C: If we take everything except w[N], we get less than w[N-1] + w[N], in which case we might as well just take w[N-1] and w[N] instead. So either way, we must take w[N].
• w[N] <= C < w[N-1] + w[N]: We cannot take both w[N-1] and w[N]. If we take neither then we get less than w[N] and should just take w[N] instead. So we must take exactly one of them.
• C < w[N]: obviously we cannot take w[N].

In the first and third cases, we know whether to take w[N], and repeat the problem using only the first N - 1 weights and any remaining capacity. In the second case, we have to branch and consider both cases, in each case solving the problem for the remaining N - 2 weights. In the worst case we will always have the second case, causing us to branch two ways at each level. However, there are only N/2 levels of recursion (because we eliminate two, rather than one, weight each time), so the running time is proportional to 2^N/2 rather than 2^N.

Here is Bruce's solution:

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
#include <cassert>
#include <cstdarg>
#include <cstdio>
#include <climits>

#define MAXN 40
#define MAXA 0x3fffffff
#define MAXC 0x3fffffff

using namespace std;

static int N, C;
static int A[MAXN];
static int best;
static long long best_used;

static long long your_used;

/* Call this to assign the score. The reason takes a printf-style
 * format string. It does not return.
 */
static void givescore(int score, const char *reason, ...) {
    va_list ap;

    printf("Score:  %d\nReason: ", score);
    va_start(ap, reason);
    vprintf(reason, ap);
    va_end(ap);
    printf("\n");
    exit(0);
}

void readin(istream &in) {
    in.exceptions(ios::failbit);

    in >> N;
    assert(1 <= N && N <= MAXN);
    in >> C;
    assert(1 <= C && C <= MAXC);
    for (int i = 0; i < N; i++)
    {
        in >> A[i];
        assert(1 <= A[i] && A[i] <= MAXA);
        assert(i == 0 || A[i - 1] <= A[i]);
        assert(i < 2 || A[i] >= A[i - 1] + A[i - 2]);
    }
}

static void readin(const string &fname) {
    if (fname != "") {
        ifstream in(fname.c_str());
        assert(in);
        readin(in);
    }
    else
        readin(cin);
}

static void recurse(int x, int gap, long long used) {
    if (x == 0) {
        if (C - gap > best) {
            best = C - gap;
            best_used = used;
        }
    } else if (x == 1) {
        if (A[0] <= gap)
            recurse(0, gap - A[0], used | 1LL);
        else
            recurse(0, gap, used);
    } else if (gap >= A[x - 1] + A[x - 2]) {
        recurse(x - 1, gap - A[x - 1], used | (1LL << (x - 1)));
    } else if (gap < A[x - 1])
        recurse(x - 1, gap, used);
    else {
        recurse(x - 2, gap - A[x - 1], used | (1LL << (x - 1)));
        recurse(x - 2, gap - A[x - 2], used | (1LL << (x - 2)));
    }
}

static void solve() {
    best = 0;
    best_used = 0;
    recurse(N, C, 0LL);
}

static void writeout(ostream &out) {
    out.exceptions(ios::failbit);

/*
    for (int i = 0; i < N; i++)
        out << ((best_used & (1LL << i)) ? 1 : 0) << "\n";
*/
    out << best  << endl;
}

static void writeout(const string &fname) {
    if (fname != "") {
        ofstream out(fname.c_str());
        assert(out);
        writeout(out);
    }
    else
        writeout(cout);
}

static void readout(const string &fname) {
    ifstream out(fname.c_str());
    assert(out);
    out.exceptions(ios::failbit);
    // try
    {
        int x;

        your_used = 0LL;
        for (int i = 0; i < N; i++) {
            out >> x;
            if (x != 0 && x != 1)
                givescore(0, "Expected 0 or 1, received %d", x);
            if (x) your_used |= 1LL << i;
        }
    }
    // catch (ios_base::failure &e)
//    {
//        givescore(0, "Invalid formatting");
//    }
}

static void evaluate() {
    long long total = 0;

    for (int i = 0; i < N; i++)
        if (your_used & (1LL << i))
            total += A[i];

    assert(total <= best || total > C);
    if (total > C) givescore(0, "Total %lld exceeds capacity %d", total, C);
    else if (total == best) givescore(10, "Optimal answer (weight of %d)", best);
    else givescore(0, "Suboptimal answer (%lld of %d)", total, best);
}

int main(int argc, char **argv) {
    if (argc <= 1) {
        readin("scales.in");
        solve();
        writeout("scales.out");
    } else {
        assert(argc > 2);
        cout << "Reading input file" << endl;
        readin(argv[1]);
        cout << "Solving problem" << endl;
        solve();

        cout << "Reading output file" << endl;
        readout(argv[2]);
        cout << "Evaluating" << endl;
        evaluate();
    }
    return 0;
}