rqnoj02 開心的金明（dp，01背包）

[cpp] 
#include <cstdio>  
const int maxm = 30000 + 10; 
const int maxn =30; 
int v[maxn], p[maxn]; 
int dp[maxm] = {0}; 
int main() 
{ 
    int n, m; 
    int i, j; 
    scanf("%d%d", &n, &m); 
    for (i = 0; i < m; i++) 
        scanf("%d%d", &v[i], &p[i]); 
    for (i = 0; i < m; i++) 
        for (j = n; j >= v[i]; j--) 
            if (dp[j - v[i]] + v[i] * p[i] > dp[j]) 
                dp[j] = dp[j - v[i]] + v[i] * p[i]; 
    printf("%d\n", dp[n]); 
    return 0; 
} 

#include <cstdio>
const int maxm = 30000 + 10;
const int maxn =30;
int v[maxn], p[maxn];
int dp[maxm] = {0};
int main()
{
 int n, m;
 int i, j;
 scanf("%d%d", &n, &m);
 for (i = 0; i < m; i++)
  scanf("%d%d", &v[i], &p[i]);
 for (i = 0; i < m; i++)
  for (j = n; j >= v[i]; j--)
   if (dp[j - v[i]] + v[i] * p[i] > dp[j])
    dp[j] = dp[j - v[i]] + v[i] * p[i];
 printf("%d\n", dp[n]);
 return 0;
}