完全背包问题

有\(n\)种物品，物品的体积分别为\(V_1,V_2,\dots,V_n\)，且每种物品的数量都可以看做是无限多的。现在有\(m\)次询问，每次询问给定一个容量为取的背包，请你回答是否存在一种物品选择方案，使得背包恰好能被完全装满（仅考虑体积，忽略长、宽、高等其他因素)。同时，要求所有选出的物品中，体积不小于\(L\)的物品总数量不能超过\(C\)件。

输入格式

第一行为两个正整数\(n\)和\(m\)，分别表示物品的种数以及询问的次数。
第二行为\(n\)个正整数\(V_1,V_2,\dots,V_n(V_i \le 10000)\)，分别表示这\(n\)种物品的体积。
第三行为两个非负整数 \(L(L \le 20000 )\) 和 \(C(C\le 30)\)，表示在选择方案中对大体积物品的数量限制。
接下来\(m\)行，每行一个正整数\(W_i\)，表示这次询问中背包的容量。

输出格式

输出共\(m\)行，每行一个字符串，表示对应询问的答案。
对于每次询问，如果存在一种合法的方案，请输出\(Yes\)，否则输出\(No\)。

数据规模与约定

对于\(10\%\)的数据：\(n\le 8,W_i\le 100\)

对于\(30\%\)的数据：\(W_i\le 10000\)

对于\(60\%\)的数据：\(n\le 30,m\le 200\)

对于另外\(10\%\)的数据：\(n=2\)

对于\(100\%\)的数据：\(n\le 50,m\le 100000,W_i\le 10^{18}\)

考虑暴力

令\(dp_{i,j,k}\)表前\(i\)个物品总体积为\(k\)选择了\(j\)件大物品的是否合法。

复杂度\(O(n\max W_i c)\)

考虑修补这个想法。设\(V_0\)为最小的体积

• 如果\(V_0\ge L\)，因为可选的物品总体积不会太大，所以考虑直接暴力，复杂度\(O(nc^2\sum V_i)\)，用\(\tt{bitset}\)

优化一下就可以过了。

• 如果\(V_0 < L\)，因为\(V_0\)可以无限选，所以我们不妨求出在同余于\(V_0\)情况下的可能，这样就简化了状态。

令\(dp_{i,j,k}\)表示前\(i\)个物品选择了\(j\)件大物品选择的总体积同余于\(V_0\)下为\(k\)的最小总体积。

保证了最小总体积，我们就可以判断\(W_i\)是否大于等于\(dp_{n,\forall j\le c,W_i \bmod V_0}\)来看是否合法

考虑转移

\(dp_{i,j,k}=\min(dp_{i,j,(v_0-v_i)\bmod v_0}+v_i,dp_{i-1,j,k}),v_i < L\)

\(dp_{i,j,k}=\min(dp_{i,j-1,(v_0-v_i)\bmod v_0}+v_i,dp_{i-1,j,k}),v_i \ge L\)

发现第一个转移有环，可以建图解决。

源点\(S\)连接所有\(0 \sim v_0-1\)的点，边权为\(dp_{i,j,v_0}\)，然后其他点每个点\(v\)连\((v+v_i)\bmod v_0\)，边权为\(v_i\)，然后跑一边最短路就可以了。

发现这个图比较特殊，可以通过寻找性质\(O(n)\)解决。

Code:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <bitset>
#define ll long long
int n,c,m,v[52],L;ll w;
int min(int x,int y){return x<y?x:y;}
namespace work1
{
std::bitset <1000001> dp[31];
void work()
{
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=c;j++)
            dp[j]|=dp[j-1]<<v[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",w);
        int ans=0;
        for(int j=0;j<=n;j++) ans|=dp[j][w];
        if(ans) puts("Yes");
        else puts("No");
    }
}
}
namespace work2
{
const int N=10010;
const int inf=0x3f3f3f3f;
int dp[31][N],used[32][N],mi,id;
#define dec(a,b) (((a-b)%v[1]+v[1])%v[1])
#define to ((now+v[p])%v[1])
void dfs0(int p,int k,int now)
{
    if(used[k][now]) return;
    used[k][now]=1;
    if(mi>dp[k][now]) mi=dp[k][now],id=now;
    dfs0(p,k,to);
}
void dfs1(int d,int p,int k,int now,int anc)
{
    if(now==anc) return;
    dp[k][now]=min(dp[k][now],d+v[p]);
    dfs1(dp[k][now],p,k,to,anc);
}
void topo(int p)
{
    memset(used,0,sizeof(used));
    for(int i=0;i<=c;i++)
        for(int j=0;j<v[1];j++)
            if(!used[i][j])
            {
                mi=inf;
                dfs0(p,i,j);
                dfs1(dp[i][id],p,i,(id+v[p])%v[1],id);
            }
}
void work()
{
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i]<L) topo(i);
        else
        {
            for(int k=0;k<=c;k++)
                for(int j=0;j<v[1];j++)
                    dp[k][j]=min(k?dp[k-1][dec(j,v[i])]+v[i]:inf,dp[k][j]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&w);
        int ans=0;
        for(int j=0;j<=c;j++)
            if(dp[j][w%v[1]]!=inf)
                ans|=dp[j][w%v[1]]<=w;
        if(ans) puts("Yes");
        else puts("No");
    }
}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",v+i);
    scanf("%d%d",&L,&c);
    std::sort(v+1,v+1+n);
    if(v[1]>=L) work1::work();
    else work2::work();
    return 0;
}

2018.10.30