题解 P2347 【砝码称重】
ShineEternal
2019-08-27 10:52:55
## 题目链接：
https://www.luogu.org/problem/P2347
## 分析：
这道题应该不难看出是一道多重背包的题目。
#### 那么我们会有两种思路：
- 按照普通的计算方式，记$f[i]$为背包容量为i时能装到的最大质量。这样最后判断能否装满$(f[i]==i)$即为能否称出一种方案
- 记$f[i]$为能否称出i的质量（$0/1$），那么最后就判断有多少个1就行。
#### 那么下面就总结两种方法：
- 普通的多重背包做法：
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
int v[10],w[10],f[10005];
int main()
{
v[1]=1;
v[2]=2;
v[3]=3;
v[4]=5;
v[5]=10;
v[6]=20;
int n=6,m;
for(int i=1;i<=6;i++)
{
scanf("%d",&w[i]);
m+=v[i]*w[i];
}
for(int i=1;i<=6;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=0;k<=w[i];k++)
{
if(j-k*v[i]<0)break;
f[j]=max(f[j],f[j-k*v[i]]+k*v[i]);
}
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(f[i]==i)
{
ans++;
}
}
printf("Total=%d\n",ans);
}
```
- 二进制优化的多重背包做法：
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
int v[10],w[100],f[10005],a[10];
int main()
{
v[1]=1;
v[2]=2;
v[3]=3;
v[4]=5;
v[5]=10;
v[6]=20;
int n=6,m;
int n1=0;
for(int i=1;i<=6;i++)
{
scanf("%d",&a[i]);
m+=a[i]*v[i];
int t=1;
while(a[i]>=t)
{
w[++n1]=v[i]*t;
a[i]-=t;
t*=2;
}
if(a[i])
w[++n1]=v[i]*t;
}
for(int i=1;i<=n1;i++)
{
for(int j=m;j>=w[i];j--)
{
f[j]=max(f[j],f[j-w[i]]+w[i]);
}
}
int ans=0;
for(int i=1;i<=m;i++)
{
if(f[i]==i)
{
ans++;
}
}
printf("Total=%d\n",ans);
return 0;
}
```