题解 | #称砝码#

//本质上是个多重背包问题
//首先用二维dp数组解决一下
#include<stdio.h>
#include<string.h>
int main(void)
{
    int n;
    scanf("%d",&n);
    int m[15]={0};
    int x[15]={0};
    int sum=0;
    int dp[15][200000]={0};//0表示不可以称出这个重量，1表示可以
    for(int i=1;i<=n;i++){scanf("%d",&m[i]);}
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
        sum+=x[i]*m[i];//计算可以称出的最大重量
    }
    //开始动态规划
    for(int i=0;i<=n;i++){dp[i][0]=1;}//dp数组初始化
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            if(dp[i-1][j]==1)
            {
                dp[i][j]=1;
            }
            else
            {
                for(int k=1;k<=x[i];k++)
                {
                    if(j>=k*m[i]&&dp[i-1][j-k*m[i]]==1)
                    {
                        dp[i][j]=1;
                        break;
                    }
                }
            }
        }
    }
    int t=0;
    for(int i=0;i<=sum;i++)
    {
        t+=dp[n][i];
    }
    printf("%d\n",t); 
    return 0;
}

//本质上是个多重背包问题
//然后用滚动dp数组解法解决一下
#include<stdio.h>
#include<string.h>
int main(void)
{
    int n;
    scanf("%d",&n);
    int m[15]={0};
    int x[15]={0};
    int sum=0;
    int dp[200000]={0};//0表示不可以称出这个重量，1表示可以
    dp[0]=1;
    for(int i=1;i<=n;i++){scanf("%d",&m[i]);}
    for(int i=1;i<=n;i++){
        scanf("%d",&x[i]);
        sum+=x[i]*m[i];//计算可以称出的最大重量
    }
    //开始动态规划
    for(int i=0;i<=n;i++)
    {
        for(int j=sum;j>=0;j--)
        {
            if(dp[j]==1){dp[j]=1;continue;}
            for(int k=1;k<=x[i];k++)
            {
              if(k*m[i]<=j&&dp[j-k*m[i]]==1)
              {
                  dp[j]=1;
                  break;
              }
            }
            
        }
    }
    int t=0;
    for(int i=0;i<=sum;i++)
    {
        t+=dp[i];
    }
    printf("%d",t);
    return 0;
}