$POJ1742\ Coins$ 多重背包+贪心

Vjudge传送门

$Sol$

首先发现这是一个多重背包，所以可以用多重背包的一般解法（直接拆分法，二进制拆分法...）

但事实是会TLE，只能另寻出路

本题仅关注“可行性”（面值能否拼成）而不是“最优性”，这是一个特殊之处。

从这里找优化

在“最优性”的问题中，$f[j]$从$f[j]$或$f[j-a[i]]$中转移而来；而在这样的“可行性”问题中，其实只要$f[j]$可行，我们就可以不用考虑$f[j-a[i]$了，也可以反过来说。

于是我们可以考虑一种贪心策略，设$used[j]$表示$f[j]$在阶段$i$时为$True$至少要用多少枚第$i$中硬币。

$f[j]$优先考虑由$f[j]$转移而来，而不是$f[j-a[i]]$，这样就尽量减少了第$i$种硬币的使用数量。

其实还可以在作一个小优化，就是直接把$used[j]$的值存在$f[j]$中,$f[]$初始为$-1$，意为不能表示。

$Code$

 #include<iostream>

 #include<cstdio>

 #define Rg register

 #define il inline

 #define db double

 #define ll long long

 #define go(i,a,b) for(Rg int i=a;i<=b;i++)

 #define yes(i,a,b) for(Rg int i=a;i>=b;i--)

 using namespace std;

 il int read()

 {

     int x=,y=;char c=getchar();

     while(c<''||c>''){if(c=='-')y=-;c=getchar();}

     while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

     return x*y;

 }

 const int N=;

 int n,m,a[N],c[N],f[];

 ll ans;

 il void sol()

 {

     go(i,,m)f[i]=-;

     go(i,,n)

         go(j,,m)

     {

         if(f[j]>=)f[j]=c[i];//f[0]=c[i]可以看成是初始化

         else if(j>=a[i]&&f[j-a[i]]>)f[j]=f[j-a[i]]-;//第i种硬币还有剩余

     }

     go(i,,m)if(f[i]>=)ans++;

 }

 int main()

 {

     while()

     {

         n=read(),m=read();ans=;

         if(!n&&!m)break;

         go(i,,n)a[i]=read();go(i,,n)c[i]=read();

         sol();printf("%lld\n",ans);

     }

     return ;

 }

巴特西

$POJ1742\ Coins$ 多重背包+贪心

最新文章

热门文章