E10 背包DP 多重背包 二进制优化

【题解】acwing 281. 硬币 [二进制优化/单调队列优化多重背包]-CSDN博客

#include <bits/stdc++.h>
using namespace std; const int N = 110, M = 1e5 + 5;
int n, m, a[N], c[N]; bool f[M];
int main()
{
    while(scanf("%d%d", &n, &m) != EOF && n && m)
    {
        memset(f, 0, sizeof(f)); f[0] = true;
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]); // 硬币面值
        for(int i = 1; i <= n; i++) scanf("%d", &c[i]); // 硬币数量
        for(int i = 1; i <= n; i++)
        {
            // 将数量c[i]分解为二进制，进行二进制优化
            for(int k = 1; k <= c[i]; c[i] -= k, k <<= 1)
            {
                int val = k * a[i];
                for(int j = m; j >= val; j--)
                {
                    if(f[j - val]) f[j] = true;
                }
            }
            // 处理剩余的c[i]
            if(c[i])
            {
                int val = c[i] * a[i];
                for(int j = m; j >= val; j--)
                {
                    if(f[j - val]) f[j] = true;
                }
            }
        }
        int ans = 0;
        for(int i = m; i >= 1; i--) if(f[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

E10 背包DP 多重背包 二进制优化
【题解】acwing 281. 硬币 [二进制优化/单调队列优化多重背包]-CSDN博客

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110],c[110],w[11000];
bool f[110000];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        int ans=0,len=0;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&c[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=c[i];j*=2)w[++len]=j*a[i],c[i]-=j;
            if(c[i]>0)w[++len]=c[i]*a[i];
        }
        memset(f,0,sizeof(f));f[0]=1;
        for(int i=1;i<=len;i++)
        {
            for(int j=m;j>=w[i];j--)if(f[j-w[i]]&&!f[j])f[j]=1;
        }
        for(int i=1;i<=m;i++)if(f[i])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=110, M=1e5+5;
int n, m, a[N], c[N]; bool f[M];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
    	memset(f, 0, sizeof(f)); f[0]=1;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&c[i]);
        for(int i=1; i<=n; i++)
        {
        	for(int k=1; k<=c[i]; c[i]-=k, k*=2)
        		for(int j=m; j>=k*a[i]; j--)
        		{
        			if(f[j-k*a[i]] && !f[j]) f[j]=1;
				}
			if(c[i])
			{
        		for(int j=m; j>=c[i]*a[i]; j--)
        		{
        			if(f[j-c[i]*a[i]] && !f[j]) f[j]=1;
				}
			}
		}
		int ans=0; for(int i=1; i<=m; i++) if(f[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}