zoj 1366 Cash Machine

01背包加变形 动态规划的时候就犯浑了，每个状态都要记录的，我却只记录了当前状态的！！

#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
 return (a) > (b) ? (a) : (b);
}
int a[12],b[12],M,dp[12][100010];

int main(){
    int N,i,j,k,ma;
    while(scanf("%d",&M)!=EOF)
    {
         scanf("%d",&N);
         ma=0;
        for(i=1;i<=N;i++)
        {
             scanf("%d %d",&a[i],&b[i]);
             ma+=a[i]*b[i];
         }
        
        if(N==0||M==0)
        {
             printf("0
");
            continue;
         }
        if(ma<=M)
        {
             printf("%d
",ma);
            continue;
         }
         memset(dp,0,sizeof(dp));
        
        for(i=1;i<=N;i++)
        {
            
            for(j=0;j<=M;j++)
            {
                for(k=0;k<=a[i];k++)
                {
                    if(j>=k*b[i])
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k*b[i]]+k*b[i]);
                 }
             }
         }
         printf("%d
",dp[N][M]);
     }
    return 0;
}