#include<cstdio>

 #include<cstring>

 int n,m,anss;

 int a[],c[],f[];

 int main()

 {

     int i,j,t;

     scanf("%d%d",&n,&m);

     while(n!=||m!=)

     {

         anss=;

         memset(f,,sizeof(f));

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(i=;i<=n;i++)

             scanf("%d",&c[i]);

         f[]=;

         for(i=;i<=n;i++)

         {

             t=;

             while(c[i]>)

             {

                 if(t>c[i])    t=c[i];

                 c[i]=c[i]-t;

                 for(j=m;j>=a[i]*t;j--)

                     f[j]|=f[j-a[i]*t];

                 t*=;

             }

         }

         for(i=;i<=m;i++)

             if(f[i])

                 anss++;

         printf("%d\n",anss);

         scanf("%d%d",&n,&m);

     }

     return ;

 }

 #include<cstdio>

 #include<cstring>

 #include<bitset>

 using namespace std;

 int n,m,anss;

 int a[],c[];

 bitset<> f;

 int main()

 {

     int i,j,t;

     scanf("%d%d",&n,&m);

     while(n!=||m!=)

     {

         anss=;

         f.reset();

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         for(i=;i<=n;i++)

             scanf("%d",&c[i]);

         f[]=;

         for(i=;i<=n;i++)

         {

             t=;

             while(c[i]>)

             {

                 if(t>c[i])    t=c[i];

                 c[i]=c[i]-t;

                 f|=(f<<(a[i]*t));

                 t*=;

             }

         }

         for(i=;i<=m;i++)

             if(f[i])

                 anss++;

         printf("%d\n",anss);

         scanf("%d%d",&n,&m);

     }

     return ;

 }

（仅做记录）④对于朴素的方法，这个算法每次只记录一个bool值，损失了不少信息。在这个问题中，不光能够求出是否能得到某个金额，同时还能把得出了此金额时A_i还剩下多少个算出来，这样直接省掉了k那重循环。

我们优化dp的状态：

状态：dp[i][j] : = 用前i种硬币凑成j时第i种硬币最多能剩余多少个（ - 1表示配不出来）

转移：

①若dp[i-1][j]>=0，即前i-1种可以配成j，所以根本用不到第i种，所以剩余C_i种  dp[i][j]=C_i

②若j<a[i] || dp[i][j-a[i]]<=0，由于dp[i-1][j]<0，所以要想配成j起码得要有第i种，若j<a[i]则第i种用不到，所以前i种仍配不到j，若dp[i][j-a[i]]<=0，则说明配成j-a[i]时第i种已经无剩余或者甚至无法配成j-a[i]，更别说配成j了，        dp[i][j]=-1

③其他情况，由于a[i]还有剩，所以dp[i][j]相当于在dp[i][j-a[i]]的基础上多使用了一个a[i]，此时   dp[i][j]=dp[i][j-a[i]]-1

最终找出所有>=0的dp[n][i]个数就行了（1<=i<=m）

#include<cstdio>

#include<cstring>

#include<bitset>

using namespace std;

int n,m,anss;

int a[],c[];

int ans[];

int main()

{

    int i,j,t;

    scanf("%d%d",&n,&m);

    while(n!=||m!=)

    {

        anss=;

        memset(ans,-,sizeof(ans));

        ans[]=;

        for(i=;i<=n;i++)

            scanf("%d",&a[i]);

        for(i=;i<=n;i++)

            scanf("%d",&c[i]);

        for(i=;i<=n;i++)

            for(j=;j<=m;j++)

                if(ans[j]>=)

                    ans[j]=c[i];

                else if(j<a[i]||ans[j-a[i]]<=)

                    ans[j]=-;

                else ans[j]=ans[j-a[i]]-;

        for(i=;i<=m;i++)

            if(ans[i]>=)

                anss++;

        printf("%d\n",anss);

        scanf("%d%d",&n,&m);

    }

    return ;

}