小弟没好好学过背包只想出这个 C++ 32ms AC

#include <cstdio>
int main()
{
    int C, N, a[11], w[11], i, j, k, p;
    while (scanf("%d", &C) != EOF)
    {
        int f[100001] = {0};
        f[0] = 1;
        scanf("%d", &N);
        for (i = 1; i <= N; i++)
        {
            scanf("%d%d", &a[i], &w[i]);
            for (k = 100000; k; k--)
                if (k - w[i] >= 0 && f[k - w[i]])
                    for (p = k, j = 0; j < a[i]; j++)
                    {
                        if (p > 100000 || f[p] == i) break;
                        f[p] = i;
                        p += w[i];
                    }
        }
        for (i = C; !f[i]; i--);
        printf("%d\n", i);
    }
}

• 另外此题数据貌似与描述不符，会导致个别童鞋WA (103) EVILsupermp5 2013-12-02 16:06:32