USACO DEC06 Problem 'eatpuz' Analysis

by Rob Kolstad

Another brute force problem, the key to the solution is the ability to generate all possible combinations of buckets to eat: a single bucket, all pairs, all triples, and so on.

One of the easiest ways to generate all the possible combinations is to count in an integer, using the bottom N bits to represent whether the bucket is to be included in the sum or not. The bits cycle through the all the possible N combinations if one counts from 0 to 1<<N (i.e., 2N).

Here's an example where N = 3; we will count from 0 through 23-1. Buckets are numbered from right to left (backwards):

   counter   binary_value      interpretation
     0           000       Buckets included: none
     1           001       Buckets included: 1
     2           010       Buckets included: 2
     3           011       Buckets included: 1,2
     4           100       Buckets included: 3
     5           101       Buckets included: 1,3
     6           110       Buckets included: 2,3
     7           111       Buckets included: 1,2,3

How to figure out whether a bit is switched on or not? Two pieces of knowledge are necessary: how to generate a single bit to represent bucket i and how to ask if that bit is set.

The bit for bucket i is 1<<(i-1) (1 shifted left i-1 times). The i-1 term is why folks usually number from 0 instead of 1 in many programming languages. Thus 1<<0 is 1, 1<<1 is 2, 1<<2 is 4, and so on. In fact, 1<<i is the same as 2i as long as you remain within the 32 bits of integers. Don't forget the highest bit is used to represent the sign of the number.

To ask if a bit is turned in some integer, the expression num&bit is used. The '&' operator between two integers returns a result whose bits are 1 only when the corresponding bits of its two terms are 1. Thus, 1 & 1 = 1 and 4 & 1 = 0.

This information combines to a compact little solution:

#include
<stdio.h>

int buckets[100];       /* bucket calories */
int B;                  /* # buckets */
int C;                  /* max calories */
int best;

main () {
    FILE *fin = fopen ("eatpuz.in", "r");
    FILE *fout = fopen ("eatpuz.out", "w");
    int i, j, sum;
    fscanf(fin, "%d %d", &C, &B);
    for (i = 0; i < B; i++)
        fscanf(fin, "%d", &buckets[i]);
    for (i = 0; i < 1<<B; i++) {
        sum = 0;
        for (j = 0; j < B; j++)
            if (i & (1<<j)) sum += buckets[j];
        if (sum > best && sum <= C) best = sum;
    }
    fprintf(fout, "%d\n", best);
    exit (0);
}

One could also solve this problem recursively:

#include <stdio.h>

int buck[24], max=0;

tryb (buckets, sum) {
    if (sum > C) return;
    if (sum>max) max=sum;
    if (buckets > 0) {
        tryb (buckets-1, sum                  );
        tryb (buckets-1, sum + buck[buckets-1]);
    }
}

int main() {
    FILE *f = fopen ("eatpuz.in", "r");
    int i, C, B;
    fscanf (f, "%d%d", &C, &B);
    for (i=0; i<B; i++)
        fscanf (f, "%d", &buck[i]);
    fclose (f);
    tryb (B, 0);
    f = fopen("eatpuz.out", "w");
    fprintf (f, "%d\n", max);
    fclose (f);
    return 0;
}