UVa 10819

0-1 knapsack problem with a tricky modification, which is the if condition in dp iteration

j==p[i]||(j>p[i]&&d[j-p[i]])

this will generate a scattered dp table, not like the original continuous one.

/* UVas */
/*****************************************************************************/
#define N 100
#define M 10201
int m, n;
int p[N];
int f[N];
int d[M];
int main(void) {
    while ( scanf("%d %d", &m, &n)>0) {
        for (int i=0; i<n; i++)
            scanf("%d %d", &p[i], &f[i]);
        memset(d, 0, sizeof(d));
        for (int i=0; i<n; i++)
            for (int j=M-1; j>=p[i]; j--)
                if (j==p[i]||(j>p[i]&&d[j-p[i]]))
                    d[j]=max(d[j], d[j-p[i]]+f[i]);
        int r=0;
        for (int i=0; i<M; i++)
            if ((i>2000&&i<=m+200)||i<=m)
                r=max(r, d[i]);
        printf("%d\n", r);
    }
}
/*****************************************************************************/