PROB: inflate 最简的多重背包问题

可以套模板的多重背包问题

因为背包容量和物品种类数都最大10000，暴力dp 需要一亿次，本来以为可能超一秒了。结果...可能是每次做的事情都太傻瓜了吧。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4176 KB]
   Test 2: TEST OK [0.000 secs, 4176 KB]
   Test 3: TEST OK [0.000 secs, 4176 KB]
   Test 4: TEST OK [0.000 secs, 4176 KB]
   Test 5: TEST OK [0.000 secs, 4176 KB]
   Test 6: TEST OK [0.000 secs, 4176 KB]
   Test 7: TEST OK [0.014 secs, 4176 KB]
   Test 8: TEST OK [0.056 secs, 4176 KB]
   Test 9: TEST OK [0.084 secs, 4176 KB]
   Test 10: TEST OK [0.098 secs, 4176 KB]
   Test 11: TEST OK [0.000 secs, 4176 KB]
   Test 12: TEST OK [0.000 secs, 4176 KB]

All tests OK.

/*
ID: ufoshen1
LANG: C++
TASK: inflate
*/

#include <cstdio>
#include <cstdlib>
#define max(a,b) ((a) > (b)? (a): (b))

int main(){
    FILE *fin = fopen("inflate.in", "r");
    FILE *fout = fopen("inflate.out", "w");

    const int maxM = 10000, maxN = 10000; //最大时间 最大种类数
    int dp[maxM + 1], M, N;
    int score[maxN], time[maxN];

    // 读入
    fscanf(fin, "%d %d", &M, &N);
    for(int i = 0; i < N; i ++){
        fscanf(fin, "%d %d", score + i, time + i);
    }

    // 初始化
    for(int i = 0; i <= M; i ++){
        dp[i] = 0;
    }

    // 多重背包问题的 dp
    for(int i = 0; i < N; i ++){
        for(int j = time[i]; j <= M; j ++){
            dp[j] = max(dp[j], dp[j - time[i]] + score[i]);
        }
    }

    fprintf(fout, "%d\n", dp[M]);
    return 0;    
}

代码我都不好意思放了……回去看了下之前写的背包问题，就直接过了……