USACO DEC07 Problem 'shelf2' Analysis

by Neal Wu

To solve this problem, we simply need to look at the sums of all 2^N subsets of the numbers. (This is possible since N <= 20, and so there are at most around one million such subsets.) There are several methods of doing this, but two fairly simple methods are the following:

The first method is to iterate over all binary numbers from 0 to 2^N - 1, inclusive. In each binary number, we can imagine it as having exactly N bits (similar to base 10 'digits'). A '1' in bit number i means that we should use cow i, while a '0' means that we should not. Thus, each binary number from 0 to 2^N - 1 represents a subset of the N cows, and in fact they represent every subset. This approach gives us a runtime of O(N 2^N).

The second method is to use recursion to generate every sum. For each cow, we have two possibilities: we either use the cow or we don't. This gives us a fairly simple solution that is O(2^N) with a medium overhead of function calls.

Both the bitmask and the recursive solutions are presented:

#include <cstdio>
using namespace std;

FILE *fout = fopen ("shelf2.out", "w");
FILE *fin = fopen ("shelf2.in", "r");

const int INF = 1000000000;
const int MAXN = 25;

int N, B;
int heights [MAXN];
int sum, best = INF;

int main () {
    fscanf (fin, "%d %d", &N, &B);

    for (int i = 0; i < N; i++)
        fscanf (fin, "%d", heights + i);

   // iterate over every bitmask
    for (int mask = 0; mask < (1 << N); mask++) {
        sum = 0;
        // calculate the sum of the subset
        for (int i = 0; i < N; i++)
            if (mask & (1 << i))           // is bit number i set?
                sum += heights [i];

        if (sum >= B && sum < best)
            best = sum;
    }

    fprintf (fout, "%d\n", best - B);


    return 0;
}

#include <cstdio>
using namespace std;

FILE *fout = fopen ("shelf2.out", "w");
FILE *fin = fopen ("shelf2.in", "r");

const int INF = 1000000000;
const int MAXN = 25;

int N, B;
int heights [MAXN];
int best = INF;

void solve (int num, int sum) {
    // update our best value
    if (sum >= B && sum < best)
        best = sum;

    // either we are finished or our current sum is worse than the best so far
    if (num == N || sum >= best)
        return;

    // two options - use the next number or not
    solve (num + 1, sum + heights [num]);
    solve (num + 1, sum);
}

int main () {
    fscanf (fin, "%d %d", &N, &B);
    for (int i = 0; i < N; i++)
        fscanf (fin, "%d", heights + i);
    solve (0, 0);
    fprintf (fout, "%d\n", best - B);
    return 0;
}