ssl1072-砝码称重【dp练习】

Description

设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），
要求：
输入方式：a1 a2 a3 a4 a5 a6
（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）
输出方式：N

（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）

Sample Input
1 1 0 0 0 0
(恭喜发现宝藏，送你一个秘密：https://www.luogu.org/team/show?teamid=4199)

Sample Output

3

解题思路

(⊙v⊙)嗯...这道题一看就是多重背包。然后还有难度吗水的不行。

代码

#include<cstdio>
using namespace std;
int a[7]={0,1,2,3,5,10,20},n,m,s[7];
int f[1001],w;
int main()
{
for (int i=1;i<=6;i++)
{
 scanf("%d",&s[i]);
 m+=s[i]*a[i];//求最大重量
}

//以上为输入
f[0]=1;
for (int i=1;i<=6;i++)
 for (int j=m;j>=a[i];j--)
   for (int k=1;k<=s[i];k++)
     f[j]+=f[j-a[i]*k];
//以上为方案数求法      
for (int i=1;i<=m;i++) if (f[i]>0) w++;//如果有这种方案就加
printf("%d",w);//输出不解释
}

总结

以上是生活随笔为你收集整理的ssl1072-砝码称重【dp练习】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。