算法1

(多重背包-二进制优化) $O(n^2logn)$

这题主要考二进制优化。
状态f[][]与多重背包得状态设置一样不过状态可以设置成bool,表示此状态能否由上一个状态转移过来。
转移f[i][j]|=f[i-1][j]表示得意思是f[i][j]能否由f[i-1][j]推出即。
这里初始化f[0][0]=1表示啥都不选且价值为0得状态合法;
这种bool f[][]得定义方式在 陪审团中lyd讲解得视频中提过一嘴。

补充一下：此类题型还有这道 砝码称重 ,可以练习一下..

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e5;

int n,num[N];
int a,b,c,d,e,f;
int sum;
bool f1[N];

int main()
{
    while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f)!=-1)
    {
    if(!a&&!b&&!c&&!d&&!e&&!f) break;
    memset(f1,0,sizeof f1);
    sum=1*a+2*b+3*c+4*d+5*e+6*f;
    if((sum/2)*2!=sum) {cout<<"Can't"<<'\n';}
    else {
        int m=sum/2;
        num[1]=a,num[2]=b,num[3]=c,num[4]=d,num[5]=e,num[6]=f;
        int cnt=1,w[N],n;
        for(int i=1;i<=6;i++)
        {
            int k=1;
            while(k<=num[i])
            {
                cnt++;
                w[cnt]=i*k;
                num[i]-=k,k*=2;
            }
            if(num[i]>0)
            {
                cnt++;
                w[cnt]=i*num[i];
            }
        }
        n=cnt;

        f1[0]=1;
        for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
        f1[j]|=f1[j-w[i]];

        if(f1[m]) cout<<"Can";else cout<<"Can't";
        cout<<'\n';
    }
    }
    return 0;
}

这一块是没优化的代码

/* f1[0][0]=1;
        for(int i=1;i<=6;i++)
        for(int j=0;j<=m;j++)
        for(int k=0;k*i<=j&&k<=num[i];k++)
        {
            f1[i][j]|=f1[i-1][j];
            if(j>=k*i) f1[i][j]|=f1[i-1][j-k*i];
        }

        if(f1[6][m]) cout<<"Can";else cout<<"Can't";
        cout<<'\n';
        */