完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
点击量：290
后效性处理+背包合法性转化…又是玄学操作，不过感觉对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;
}
说点什么