[文章目录]
Description
农夫John想到镇上买些补给。为了高效地完成任务，他想使硬币的转手次数最少。即使他交付的硬币数与找零得到的的硬币数最少。 John想要买T(1<=T<=10000)样东西。有N(1<=n<=100)种货币参与流通，面值分别为V1,V2..Vn (1<=Vi<=120)。John有Ci个面值为Vi的硬币(0<=Ci<=10000)。我们假设店主有无限多的硬币，并总按最优方案找零。
分组背包+完全背包，然后扫一遍就是答案。注意背包上限需要设的足够大。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int b1[20000],b2[20000],n,m,mx;
int w[200],c[200];
int main()
{
scanf("%d%d",&n,&m); mx=m<<1;
for(int i=1;i<=n;++i) scanf("%d",w+i);
for(int i=1;i<=n;++i) scanf("%d",c+i);
memset(b1,0x3f,sizeof b1); b1[0]=0;
memset(b2,0x3f,sizeof b2); b2[0]=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=c[i];c[i]-=j,j<<=1)
{
for(int k=mx;k>=j*w[i];--k)
b1[k]=min(b1[k],b1[k-j*w[i]]+j);
}
if(c[i])
{
for(int k=mx;k>=c[i]*w[i];--k)
b1[k]=min(b1[k],b1[k-c[i]*w[i]]+c[i]);
}
for(int k=w[i];k<=mx;++k)
b2[k]=min(b2[k],b2[k-w[i]]+1);
}
int ans=0x3f3f3f3f;
for(int i=m;i<=mx;++i)
{
if(b1[i]==0x3f3f3f3f||b2[i-m]==0x3f3f3f3f) continue;
ans=min(ans,b1[i]+b2[i-m]);
}
if(ans==0x3f3f3f3f) puts("-1");
else printf("%d",ans);
return 0;
}