poj_1276

dp[i] 代表能否凑出总数为i的cash
 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int n[11], d[11], cash, N;
 5 bool dp[100010];
 6 
 7 int main(int argc, char const *argv[])
 8 {
 9     // freopen("in", "r", stdin);
10     while(~scanf("%d%d", &cash, &N)){
11         for(int i = 1; i <= N; ++i)
12             scanf("%d %d", &n[i], &d[i]);
13         memset(dp, false, sizeof(dp));
14         dp[0] = true;
15         for(int i = 1; i <= N; ++i)
16             for(int j = cash; j >= 0; --j)
17                 if(dp[j] == true)
18                     for(int k = 1; k <= n[i]; ++k){
19                         if( j + k*d[i] > cash )
20                             break;
21                         dp[j + k*d[i]] = true;
22                     }
23         for(int i = cash; i >= 0; --i)
24             if(dp[i] == true){
25                 printf("%d
", i);
26                 break;
27             }
28     }
29     return 0;
30 }