学步园

思路：原版多重背包模版，直接用就行，不理解的看一多重背包的讲解（很详细）

//556K   
47MS
#include <stdio.h>
#include <string.h>
#define M 100010
#define N 15

int dp[M],count[N],val[N];
int money;

int max (int a,int b)
{
    return a
> b ? a : b;
}
void MulPack (int cost,int amount)
{
    int v
;
    if
(cost*amount >=
money)        
//完全背包
    {
       
for (v = cost;v <= money;v ++)
           
dp[v] = max (dp[v],dp[v-cost] + cost);
       
return ;
    }
    int k =
1;
    while (k
< amount)
    {
       
for (v = money;v >= k*cost;v
--)   //分解成多个0/1背包
           
dp[v] = max (dp[v],dp[v-k*cost] + k*cost);
       
amount -= k;
       
k *= 2;
    }
    for (v =
money;v >= amount*cost;v --)
       
dp[v] = max (dp[v],dp[v-amount*cost] + amount*cost);
}

int main ()
{
    int
n,i;
    while
(~scanf ("%d%d",&money,&n))
    {
       
memset (dp,0,sizeof(dp));
       
for (i = 0;i < n;i ++)
           
scanf
("%d%d",&count[i],&val[i]);
       
for (i = 0;i < n;i ++)
           
MulPack(val[i],count[i]);
       
printf ("%d\n",dp[money]);
    }
}