完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】

作者: wjyyy 分类: DP,同余,图论,最短路,有后效性的DP,背包,解题报告 发布时间: 2018-10-31 15:43

点击量:88

 

    后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。

 

题目描述

有\(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

输入输出样例

输入样例1:

3 2
3 22 29
100 0
19
39394684982

输出样例1:

No
Yes

输入样例2:

4 4
4 4 5 7
5 1
2 
4
28
14

输出样例2:

No
Yes
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}\)

题解:

    这个题是完全背包,而且这个背包很完全,询问的数据范围达到了\(10^{18}\)级别,显然一般的DP做不了这样的范围。不过对于前\(30\%\)的数据,还是比较基础的完全背包的。

部分分特殊解:

    先考虑下\(n=2\)的特殊数据,就是求解\(v_1x+v_2y=w\)的解的情况。如果这个方程无解,直接输出No,否则进行下一步判断。我们要使超过\(L\)的物品数尽可能少,就要尽可能多地选较贵的那一个,此时涉及到二元一次不定方程的通解问题,证明见扩展欧几里得学习笔记。如果\(v_1<L\)且\(v_2<L\),则只需要看是否存在非负整数解。否则令\(v_1\le v_2\),如果只有\(v_2\ge L\)则令\(x\)尽可能大,即\(y\)尽可能小。还有一种情况是\(v_1\ge L\)且\(v_2\ge L\),此时让\(x\)尽可能小,使得\(x+y\)尽可能大。事实证明这里貌似没什么影响,只需要判非负整数解。因为我写失误了一次还过了2333…代码实现如下

点我跳过代码

#include<cstdio>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
int main()
{
    int n,m,L,C;
    scanf("%d%d",&n,&m);
    ll a,b,w,x,y;
    scanf("%lld%lld",&a,&b);
    scanf("%d%d",&L,&C);
    if(a>b)//默认把小的放在前面
    {
        ll t=a;
        a=b;
        b=t;
    }
    ll g=exgcd(a,b,x,y);//g表示最大公约数
    a/=g,b/=g;
    exgcd(a,b,x,y);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&w);
        if(w%g)
        {
            puts("No");
            continue;
        }
        ll _x=w/g*x;
        ll _y=w/g*y;
        _x=(_x%b+b)%b;//找通解
        if((w-_x*a*g)%(b*g))//如果推出_y不是整数说明无解
        {
            puts("No");
            continue;
        }
        _y=(w-_x*a*g)/(b*g);
        if(_y<0||_x*(a>=L)+_y*(b>=L)>C)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}

正解:

    正解利用了完全背包最基础的性质,物品无限,但是需要数据分治。假设所有物品中体积最小是\(V_0\),如果\(V_0\ge L\),那么背包中最多装下\(C\)个物品,背包上界为\(\sum_{i=1}^nV_i\)。这时用\(\tt bitset\)直接做背包,f[i]|=f[i]<<v[i];。每次\(\tt bitset\)循环\(\frac{\sum_{i=1}^nV_i}{V_i}\)次。时间复杂度是\(O(\frac{nC\sum V}{\omega})\)。

    如果\(V_0<L\),那么认为当存在一种方案使得容量为\(r\)时,也存在容量为\(kV_0+r,k\in\bf N\)的方案。对于给定的\(W_i\)我们只需要判断是否存在容量为\(t\equiv W_i\pmod{V_0},t\le V_0\)的方案就可以了,因为\(V_0\)不受体积大于等于\(L\)个数的约束,所以\(V_0\)是一定可以选无限个的。对于其他\(V_i<L\)的物品的选择,我们在后面的转移会提到。

    我们依旧做完全背包,但是容量维是在\(\bmod V_0\)意义下进行的,并且要注意体积大于等于\(L\)的个数。设\(f[i][j][k]\)表示当前已经选了\(i\)个物品,选了\(j(j\le C)\)个体积超过\(L\)的物品,体积对\(V_0\)取模为\(k\)这一状态下的最小体积,最小是与上一段判断存在性有关的。转移方程就变成了

\[f[i][j][k]=\left\{\begin{matrix}
\min(f[i-1][j][k],f[i][j-1][(k-V_i)\bmod{V_0}])& ,V_i\ge L\\
\min(f[i-1][j][k],f[i][j][(k-V_i)\bmod{V_0}])& ,V_i<L\end{matrix}\right.\]

    可以看出,第二行\(V_i<L\)是有后效性的,也就是同层转移来源的最后一维不能保证与当前\(k\)的大小,并且这时\(V_i\)可以选无限个。我们对DP转移建出状态转移图,那么设一个本不存在的源点\(S\),以及\(V_0\)个点分别表示对\(V_0\)取模后得到的值,那么\(S\rightarrow x(x\in[0,V_0))\)的权值就是\(f[i-1][j][x]\)。每个点向转移方向连一条边,转移方向是\((x+V_i)\bmod{V_0}\),做出的贡献是\(V_i\),因此\(x\rightarrow (x+V_i)\bmod{V_0}\)的权值是\(V_i\)。从源点到各个点的最短路的意义就是转移后这个点的DP值,联系上面的方程可以看出,本来为每个点提供的DP值就是\(f[i-1][j][k]\),然后可以通过与后面转移方程比较大小来更新值。而最短路模型其实就是有后效性的DP,只是因为最短路有贪心算法,所以我们建出状态转移图可以把一个DP题转化到最短路上来做。

    又因为每个点可以通过前面一个点或者源点连接过来,根据最短路的不断更新,整个剩余系都会被更新成最优解,而选择无论多少个元素,体积和对\(V_0\)取模都有一个值,因此也就保证了其他\(V_i<L\)的物品也是无限选择的。使用\(\text{Dijkstra}\)求最短路,时间复杂度为\(O(nCV_0\log V_0)\)。不过也可以去掉图中最长的边跑拓扑排序,这样就成了DP套DP,时间复杂度为\(O(nCV_0)\),不过最短路还是稳一些吧拓扑排序常数有点大

Code:

#include<cstdio>
#include<cstring>
#include<bitset>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
using std::bitset;
using std::min;
using std::priority_queue;
int v[55];
int n,m,L,C;
namespace _
{
bitset<301000> f[35];
void work()
{
    f[0][0]=1;
    for(int i=1;i<=n;++i)//直接拿300000作为背包最大可能容量
    {
        int up=300000/v[i]+1;
        for(int j=1;j<=C;++j)
        {
            f[j]|=f[j-1]<<v[i];
            for(int k=1;k<=up;++k)
                f[j]|=f[j]<<v[i];
        }
    }
    long long w;
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&w);
        if(w>300000)
            puts("No");
        else
        {
            int flag=0;
            for(int j=0;j<=C;++j)
                if(f[j][w])
                {
                    flag=1;
                    puts("Yes");
                }
            if(!flag)
                puts("No");
        }
    }
    return;
}
}
namespace __
{
struct edge
{
    int n,nxt;
    long long v;
    edge(int n,int nxt,long long v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[100000];
int head[10005],ecnt=-1;
void init()
{
    memset(head,-1,sizeof(head));
    ecnt=-1;
}
void add(int from,int to,long long v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
}
long long dis[10010];
struct statu
{
    int n;
    long long dis;
    statu(int n,long long dis)
    {
        this->n=n;
        this->dis=dis;
    }
    statu(){}
    friend bool operator <(statu a,statu b)
    {
        return a.dis>b.dis;
    }
};
void dijk(int s)
{
    priority_queue<statu> q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push(statu(s,0));
    while(!q.empty())
    {
        statu k=q.top();
        q.pop();
        if(dis[k.n]<k.dis)
            continue;
        for(int i=head[k.n];~i;i=e[i].nxt)
            if(dis[e[i].n]>k.dis+e[i].v)
            {
                dis[e[i].n]=k.dis+e[i].v;
                q.push(statu(e[i].n,dis[e[i].n]));
            }
    }
}
long long f[35][10010];
void work(int V)
{
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;++i)
        if(v[i]>=L)//直接转移
            for(int j=1;j<=C;++j)
                for(int k=0;k<V;++k)
                    f[j][k]=min(f[j][k],f[j-1][((k-v[i])%V+V)%V]+v[i]);
        else//建立图论模型
            for(int j=0;j<=C;++j)
            {
                init();
                for(int k=0;k<V;++k)
                {
                    add(V,k,f[j][k]);
                    add(k,(k+v[i])%V,v[i]);
                }
                dijk(V);
                for(int k=0;k<V;++k)
                    f[j][k]=dis[k];
            }
    long long w;
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&w);
        int flag=0;
        for(int j=0;j<=C;++j)
            if(f[j][w%V]<=w)//如果存在不超过这个数的背包则有解
            {
                flag=1;
                puts("Yes");
                break;
            }
        if(!flag)
            puts("No");
    }
    return;
}
}
int main()
{
    scanf("%d%d",&n,&m);
    v[0]=inf;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
        v[0]=v[0]<v[i]?v[0]:v[i];
    }
    scanf("%d%d",&L,&C);
    if(v[0]>=L)//数据分治
        _::work();
    else
        __::work(v[0]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */