281. 硬币 - AcWing （多重背包，巧妙优化）

• 容易想到暴力 O ( n m C i ) O(nmC_i) O(nmCi​)，显然会 T T T

#include 
using namespace std;

const int N=105,M=1e5+5;
int a[N],c[N];
int f[M],g[M];
signed main()
{
	int n,m;
	while(cin>>n>>m && n)
	{
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>c[i];
		for(int i=1;i<=m;i++) f[i]=0;
		f[0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=c[i];j++)
            {
                for(int k=m;k>=a[i];k--) if(f[k-a[i]]) f[k]=1;
            }
		}
		int ans=0;
		for(int i=1;i<=m;i++) if(f[i]) ans++;
		cout< 
考虑优化，多重背包的优化方式有两种，二进制和优先队列，但都被这题卡常了
这题有个十分巧妙的优化： 
  

       
        
         
          
           f
          
          
           [
          
          
           j
          
          
           ]
          
         
         
          f[j]
         
        
       f[j] 存在的条件：
       
        
         
          
           f
          
          
           [
          
          
           j
          
          
           −
          
          
           a
          
          
           [
          
          
           i
          
          
           ]
          
          
           ]
          
         
         
          f[j-a[i]]
         
        
       f[j−a[i]] 
       
        
         
          
           o
          
          
           r
          
         
         
          or
         
        
       or 
       
        
         
          
           f
          
          
           [
          
          
           j
          
          
           −
          
          
           2
          
          
           ∗
          
          
           a
          
          
           [
          
          
           i
          
          
           ]
          
          
           ]
          
         
         
          f[j-2*a[i]]
         
        
       f[j−2∗a[i]] 
       
        
         
          
           o
          
          
           r
          
         
         
          or
         
        
       or 
       
        
         
          
           .
          
          
           .
          
          
           .
          
         
         
          ...
         
        
       ... 
       
        
         
          
           o
          
          
           r
          
         
         
          or
         
        
       or 
       
        
         
          
           f
          
          
           [
          
          
           j
          
          
           −
          
          
           c
          
          
           [
          
          
           i
          
          
           ]
          
          
           ∗
          
          
           a
          
          
           [
          
          
           i
          
          
           ]
          
          
           ]
          
         
         
          f[j-c[i]*a[i]]
         
        
       f[j−c[i]∗a[i]] 存在
所以可以另开一个数组 
       
        
         
          
           g
          
         
         
          g
         
        
       g，记录上一个状态 
       
        
         
          
           f
          
          
           [
          
          
           j
          
          
           −
          
          
           a
          
          
           [
          
          
           i
          
          
           ]
          
          
           ]
          
         
         
          f[j-a[i]]
         
        
       f[j−a[i]] 用了多少个 
       
        
         
          
           a
          
          
           [
          
          
           i
          
          
           ]
          
         
         
          a[i]
         
        
       a[i]
 
 
#include 
using namespace std;

const int N=105,M=1e5+5;
int a[N],c[N];
int f[M],g[M];
signed main()
{
	int n,m;
	while(cin>>n>>m && n)
	{
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>c[i];
		for(int i=1;i<=m;i++) f[i]=0;
		f[0]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=m;j++) g[j]=0;
			for(int j=a[i];j<=m;j++) // 遍历从前往后
			{
				if(!f[j] && f[j-a[i]] && g[j-a[i]]