背包问题 DP

各种各样的基础背包

0-1 背包

非常朴素，复杂度 \(O(nV)\)

void z_o_pack(int c,int v)
{
	 for(int i=V;i>=c;i--)
	 	 dp[i]=max(dp[i],dp[i-c]+v);
}
           

完全背包

复杂度 \(O(nV)\)

void comp_pack(int c,int v)
{
	 for(int i=c;i<=V;i++)
	 	 dp[i]=max(dp[i],dp[i-c]+v);
}
           

多重背包

这里的写的是单调队列优化的多重背包。

复杂度可以达到 \(nV\)

int ql,qr;
struct QUE
{
	 int num,val;
}que[Maxv];
void many_pack(int c,int w,int m)
{
	 if(!c) { add+=m*w; return; }
	 m=min(m,V/c);
	 for(int pos=0,s;pos<c;pos++)
	 {
	 	 ql=1,qr=0,s=(V-pos)/c;
	 	 for(int j=0;j<=s;j++)
	 	 {
	 	 	 while(ql<=qr && que[qr].val<=(dp[pos+j*c]-j*w)) qr--;
	 	 	 que[++qr]=(QUE){j,dp[pos+j*c]-j*w};
	 	 	 while(ql<=qr && (j-que[ql].num)>m) ql++;
	 	 	 dp[pos+j*c]=max(dp[pos+j*c],que[ql].val+j*w);
		 }
	 }
}
           

多维限制背包

只是多加几位，没有太大区别。

for(int i=1;i<=n;i++)
{
	 if(/*是0-1背包*/) z_o_pack(c[i],w[i]);
	 if(/*是完全背包*/) comp_pack(c[i],w[i]);
	 if(/*是多重背包*/) many_pack(c[i],w[i],m[i]);
}
           

分组背包

同一组内只能选一个物品。

for(int i=1;i<=n;i++)
	 for(int j=V;j>=0;j--)
	 	 for(int k=1;k<=cnt[i];k++) if(j>=c[i][k])
	 	 	 dp[j]=max(dp[j],dp[j-c[i][k]]+w[i][k]);
           

这样保证每一组内只会选择一个。

很多背包问题都能都转化为分组背包。

树形依赖背包

复杂度：\(O(n^2)\)

虽然有三层循环，但是内层运算总量与整棵子树内点对个数一致。

void dfs(int x,int fa)
{
	 dp[x][1]=w[i],siz[x]=1;
	 for(int i=hea[x];i;i=nex[i])
	 {
	 	 if(ver[i]==fa) continue;
	 	 dfs(ver[i],x);
	 	 siz[x]+=siz[ver[i]];
	 	 for(int j=min(V+1,siz[x]);j>=2;j--)
	 	 	 for(int k=1;j-k>=1;k++)
	 	 	 	 dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[ver[i]][k]);
	 }
}

for(int i=1;i<=n;i++) if(!ind[i]) add(0,i); // 给出的图是一个森林
dfs(0,-1);
printf("%d\n",dp[0][V+1]);
           

泛化物品

不同问法的背包问题

输出方案

求字典序最小的方案

求方案总数

求最优方案总数

求次优解、第K优解

常见例题：

P1941 飞扬的小鸟