题目

这道题，刚开始题没读懂，就是这句话：,A1,A2,A3...An and C1,C2,C3...Cn corresponding to the number of Tony's coins of value ，

原本是A1,A2,A3...An 代表 价值

C1,C2,C3...Cn  代表 数量

结果理解反了。题都读了一下午，真的是……唉……

题意：

一位同学想要买手表，他有n种硬币，每种硬币已知有num[i]个。已知手表的价钱最多m元，问她用这些钱能够凑出多少种价格来买手表。

又或是：

题意：Tony想要买一个东西，他只有n中硬币每种硬币的面值为a[i]每种硬币的数量为c[i]要买的物品价值不超过m

输入：第一行输入n和m，第二行输入n个硬币的面值和n个硬币的数量，输入0 0结束

输出：1到m之间有多少价格Tony可以支付

代码如下：

#include<stdio.h>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 100+5;

const int M =1e5+10;

int value[N];

int value1[M];

int jian[N];

int dp[M];

int n,m;

void solve()

{

    int cnt =0;

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

    {

        for(int j=1; j<=jian[i]; j<<=1)

        {

            value1[cnt]=value[i]*j;

            jian[i]-=j;

            cnt++;

        }

        if(jian[i]>0)

        {

            value1[cnt]=value[i]*jian[i];

            cnt++;

        }

    }

    for(int i=0; i<cnt; i++)

        for(int j=m; j>=value1[i]; j--)

        {

            if(dp[j]<dp[j-value1[i]]+value1[i])

            {

                dp[j]=dp[j-value1[i]]+value1[i];

            }

        }

    int sum=0;

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

    {

        if(i==dp[i]) sum++;

    }

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

}

int main()

{

   while(  ~scanf("%d%d",&n,&m))

    {

        if(n==0&&m==0) break;

        memset(dp,0,sizeof(dp));

        memset(value,0,sizeof(value));

        memset(value1,0,sizeof(value1));

        memset(jian,0,sizeof(jian));

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

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

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

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

        solve();

    }

    return 0;

}