部分背包

有n个物体,第i个物体重量为wi,价值为vi,在总重量不超过C的情况下使总价值最高(每个物体可以取走一部分)
这是不是一个dp问题,而是贪心。
只需按性价比排序依次选取即可。

01背包

有n个物体,第i个物体重量为wi,价值为vi,在总重量不超过C的情况下使总价值最高

d(i,j) 表示 前i个货物装入容量为j的背包的最大重量 最优解d(n,C)

$$d(i,j)=Max(d(i-1,j),d(i-1,j-W[i])+V[i])$$

1
2
3
4
5
6
7
for(int i=1;i<=n;++i){
scanf("%d %d",&V,&W);
for(int j=0; j<=C; ++j){
d[i][j]=(i==1?0:d[i-1][j]);
if(j>=W) d[i][j]=max(d[i][j],d[i-1][j-W]+V);
}
}

使用滚动数组

(注意j的枚举顺序)因为d[j]保存的是d(i-1,j)的值 最优解d(C)

1
2
3
4
5
6
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i){
scanf("%d %d",&V,&W);
for(int j=C; j>=W; --j)
d[j]=max(d[j],d[j-W]+V);
}

恰好装满背包

最优解 d(ans)

1
2
3
4
5
6
7
8
memset(d,0x8f,sizeof(d));	//赋-INF
for(int i=1;i<=n;++i){
scanf("%d %d",&V,&W);
for(int j=C; j>=W; --j)
d[j]=max(d[j],d[j-W]+V);
}
int ans=C;
for(int j=C-1;j>=0;--j) if(d[ans]>d[j]) ans=j;

打印解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int f[maxC];
memset(d,0x8f,sizeof(d));
for(int i=0;i<n;++i) scanf("%d %d",v[i],w[i]);
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i){ //枚举顺序影响打印顺序
for(int j=C; j>=w[i]; --j)
if(d[j]<d[j-w[i]]+v[i]) // <字典序最小 ≤字典序最大
d[j]=d[j-w[i]]+v[i]),f[j]=i;
}
for(int j=C-1;j>=0;--j) if(d[ans]>d[j]) ans=j;

void print_ans(int d[],int C){ //调用print_ans(f,ans);
while(C){
printf("%d ",f[C]);
C-=w[f[C]];
}
}

完全背包

有n种物体(每种无限个),第i个物体重量为wi,价值为vi,在总重量不超过C的情况下使总价值最高
可以转化成以C为起点,wi为节点,vi为权值,求DAG上的最长路

d(i)表示以i为起点的最长路最优解为 d(C)

$$d(i)=Max(d(j-w[i])+v(i) \,\,|\,\, j-w[i]>0)$$

或者背包九讲的理解

$$d(i,j)=Max(d(i-1,j),d(i,j-W[i])+V[i])$$

有两种写法

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int INF=0x3f3f3f3f;
memset(vis,0,sizeof(vis));
int dp(int C){
if(vis[C]) return d[C];
vis[C]=1;
int &ans=d[C];
int ans=-INF;
for(int i=0;i<n;++i)
if(C>=w[i]) ans=max(ans,dp(S-w[i])+v[i]);
return ans;
}

const int INF=0x3f3f3f3f;
for(int i=1;i<=C;++i) dmin[i]=INF,dmax[i]=-INF;
dmin[0]=dmax[0]=0;

for(int i=0;i<n;++i) //两层循环可以颠倒
for(int j=w[i];j<=C;++j){
if(dmin[i]>dmin[i-w[i]]+v[i]){ //字典序最小的解,改成≥为字典序最大解,下面同理
dmin[i]=dmin[i-w[i]]+v[i];
min_ans[j]=i;
}
if(dmax[i]<dmax[i-w[i]]+v[i]){
dmax[i]=dmax[i-w[i]]+v[i];
max_ans[j]=i;
}
}

void print_ans(int d[],ins C) //调用 print_ans(max_ans,C) 和 print_ans(min_ans,C)
{
while(C){
printf("%d ",d[C]);
C-=w[d[C]];
}
}

递推排列组合问题

1
2
3
4
5
6
7
8
9

const int w[6]={1,5,10,20,50,100}
long long d[100+5];
memset(d,0,sizeof(d));
d[0]=1;
for(int i=0;i<6;++i)
for(int j=w[i];j<=100;--j)
d[j]+=d[j-w[i]];
return d[100];

多重背包

有n种物体,第i个物体重量为wi,价值为vi,有mi件,在总重量不超过C的情况下使总价值最高

$$d(i,j)=Max(d(i-1,j-kv[i])+kv[i])\,\,|\,\, 0 \le k \le m[i])$$

  • 先把两种种背包问题格式化一下:
1
2
3
4
5
6
7
8
9
10
11
12
void ZeroOnePack(int d[],int w,int v)
{
for(int j=C;j>=w;--j)
d[j]=max(d[j],d[j-w]+v);

}

void ConpletePack(int d[],int w,int v)
{
for(int j=w;j<=C;++j)
d[j]=max(d[j],d[j-w]+v);
}
  • 可以发现第一层枚举顺序可以任意

一般解法

一般的复杂度$O\left(nC\sum m[i]\right)$,下面用优化到了$O\left(nC\sum \log{m[i]} \right)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void MultiplePack(int d[],int w,int v,int m)
{

if(w*m>=C){
CompletePack(d,w,v);
return;
}
int k=1;
while(k<m){
ZeroOnePack(d,k*c,k*w)
m-=k;
k*=2;
}
ZeorOnePack(d,w*m,v*m);
}

单调队列优化

复杂度为$O(nC)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Queue{
int num,value;
} que[maxn];
int back,front;
int d[maxn];

void Insert(int n,int v){ //单调队列,保证队首元素为最大值
while(que[back].value<v && front<=back) --back;
que[++back].num=n;
que[back].value=v;
}

memset(d,0,sizeof d);
for(int i=0;i<n;++i){
for(int j=0;j<w[i];++j){ //枚举余数j
front=1,back=0; //清空队列
for(int k=0;k<=(C-j)/w[i];++k){ //k*w[i]+j 枚举相同余数的体积
Insert(k,d[k*w[i]+j]-k*v[i]); //入队
if(que[front].num<k-m[i]) ++front; //队首元素失效
d[k*w[i]+j]=que[front].value+k*v[i];//更新当前元素
}
}
}

混合背包

即混合上述三种背包的问题。

1
2
3
4
5
for(int i=0;i<n;++i){
if(ZeroOne) ZeroOnePack(d,w[i],v[i]);
else if(Complete) CompletePack(d,w[i],v[i]);
else if(Multiple) MultiplePack(d,w[i],v[i]);
}

当伪代码吧…

二维费用背包

有n种物体,第i种物体重量为wi,体积为vi,价值为ti,在总重量不超过C和总体积不超过V的情况下使总价值最高
状态增加一维就可以了,d(i,j,k)表示前i个物体装入容量为j,容积为k的背包可得最大价值

$$d(i,j,k)=Max(d(i-1,j,k),d(i-1,C-w[i],V-v[i])+t[i])$$

1
2
3
4
for(int i=0;i<n;++i)
for(int j=C;j>=w[i];--j) //根据条件要求递推顺序不同
for(int k=V;k>=v[i];--k)
d[j][k]=max(d[j][k],d[j-w[i]][k-v[i]]+t[i]);

  • 无论增加多少维都同理
  • 有时候,增加的维度以限制取物品个数给出,限制V件,每件的消耗都是1

第K优解

基本思想是,将每个状态都表示成有序队列,将状态转移方程中的 max/min 转化成有序队列的合并。

问题转化

一个集合中选几个数字使结果恰好为0

一个集合中选几个数字使结果恰好为总和一半

参考资料