题解 | #称砝码#
称砝码
https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
这题目应该规定一个最大重量的。不然会导致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;
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];}
//printf("%d\n",sum);
int dp[15][200000]={0};
//dp数组初始化
for(int i=0;i<=n;i++){dp[i][0]=1;}
//for(int i=1;i<=sum;i++){dp[0][i]=0;}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
if(dp[i-1][j]==1)
{
dp[i][j]=1;
continue;
}
for(int k=1;k<=x[i];k++)
{
if(j>=k*m[i])
{
if(dp[i-1][j-k*m[i]]==1){dp[i][j]=1;break;}
}
}
}
}
//遍历dp数组，找出重量种类数
int kinds=0;
for(int i=0;i<=sum;i++)
{
kinds+=dp[n][i];
}
printf("%d\n",kinds);
return 0;
}
好未来公司福利 52人发布
