USACO DEC08 Problem 'hay4sale' Analysis

by Rob Kolstad

This is a traditional knapsack problem. The solution, which many say is one sort of dynamic programming, goes like this:

• Set up an array whose contents indicate that the value indicated by the index can be achieved (in this case by using 0 or 1 occurrences of some bale of hay)
• mark array[0] as true -- volume 0 is achievable
• foreach volume (in this case, a hay bale's volume)
  • mark array[volume] as achievable
  • work through the array marking index i+volume as 'achievable' if index i is 'achievable'
• search backwards from the highest possible volume (usually, the capacity) to find the best achievable volume

China's Caima Moon's solution is shown below; it's a bit trickier than a standard implementation:

#include <cstdio>
#define oo 5005
#define mm 50005
bool f[mm];
int a[oo],N,M,ans;

int main() {
    freopen ("hay4sale.in", "r", stdin);
    freopen ("hay4sale.out", "w", stdout);
    
    scanf ("%d%d", &M, &N);
    for (int i = 1; i<=N; ++i)
        scanf("%d", &a[i]);
    
    f[0] = true;
    for (int i = 1; i <= N; i++) {
        for (int j = M; j >= a[i]; j--)
            f[j] |= f[j-a[i]];
        if (f[M]) break;
    }
    
    for (ans=M; !f[ans]; ans--)
        ;
    
    printf("%d\n", ans);
    return 0;
}