背包问题学习笔记(2)-问法的变化

所有问法均以01背包问题为例,问题如下: 有\(N\)种物品和一个容量为\(V\)的背包,每种物品都有无限件可用。放入第i种物品的费用是\(C_i\),价值是\(W_i\),求背包所装物体的价值最大。 基本代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include
using namespace std;
const int N=4,V=10;
int F[N+1][V+1];
int C[N+1]={0,3,4,4,5};
int W[N+1]={0,4,6,6,7};
void BasicZeroOnePack() //O(NV)
{
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
if(v>=C[i]) //可以加入的时候考虑一下
F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
}
}
}

改动都是基于这个代码。

恰好装满的要求

如果要求恰好装满的话,初始化时除了\(F[0]=0\)以外,其余的F[1,…V]均设为负无穷。因为如果要求恰好装满,初始化的时候只有容量为0的背包装容量为0的物体才是合法状态,其余的状态全都不合法,用负无穷表示。

输出方案

如果需要输出方案,我们只需逆推状态转移方程,确定这个状态是由哪一个策略所推出的,从而找到上一个状态即可。可以用\(G[i,v]\)记录来自哪个状态,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int G[N+1][V+1];
void BasicZeroOnePackCase()//O(NV)
{
memset(F,0,sizeof(F));
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
G[i][v]=0;
if(v>=C[i]) //可以加入的时候考虑一下
{
F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
if(F[i-1][v-C[i]]+W[i]>F[i-1][v])
G[i][v]=1;
}
}
}
}

其实不记录也可以,我们可以直接根据\(F[i][v]\)是否等于\(F[i-1][v-C[i]]+W[i]\)的值判断得到。

输出字典序最小

所谓的”字典序最小“就是按字典排序方式,1到N号物体的选择方案排列最靠前。很明显的1肯定比2靠前,也就是说我们尽量要选择前面的物体,由于我们原先的子问题”1..i个物体,背包容量j“会分解为”1…,i-1,背包容量j“和”1…i-1,背包容量j-C[i]“两个子问题并不符合字典序的假设,因为即使第i个物体服从字典序,也无法确定前i-1个物体是否服从字典序,因为1…i-1这个子问题已经被处理过了。

于是我们把循环顺序倒过来,子问题变成了“i..1个物体,背包容量j”会分解为“i-1…,1,背包容量j”和“i-1…1,背包容量\(j-C[i]\)”两个子问题,这样只要i做了服从字典序的选择,那我们只要去继续探究i-1…1这个子问题就好了。 所以我们把状态转移方程改成这样 \[ F[i,v]=\max\{F[i+1][v],F[i+1][v-C_i]+W_i\}\] 代码也只要把i逆序,i-1变成i+1即可。在输出的时候,如果\(F[i+1][v]==F[i+1][v-C_i]+W_i\)相等,尽量选加入i的策略,因为物品i必定比i+1靠前。代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void BasicZeroOnePackDictionaryOrder()
{
memset(F,0,sizeof(F));
for(int i=N;i>=1;i--)//反向定义
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i+1][v]; //默认不加入物品
if(v>=C[i]) //可以加入的时候考虑一下
F[i][v]=max(F[i+1][v],F[i+1][v-C[i]]+W[i]);
}
}
int v=V;
for(int i=1;i<=N;i++)
{
if(F[i][v]==F[i+1][v-C[i]]+W[i])
{
cout<<i<<" ";
v=v-C[i];
}
}
cout<<endl;
}

求方案总数

求方案总数一般只要把状态转移方程中的max改成sum,子问题定义为“可行的方案数”即可,要注意初始条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BasicZeroOnePackSum()
{
memset(F,0,sizeof(F));
F[0][0]=1;
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
if(v>=C[i]) //可以加入的时候考虑一下
F[i][v]=sum(F[i-1][v],F[i-1][v-C[i]]);
}
}
}

求最优方案总数

最优方案就是总价值最大的方案。这个时候只要跟着原01背包的策略走,哪个策略好就用哪个策略的方案数,如果一样好就把2个策略的方案数相加即可。

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
void BasicZeroOnePackBestSum()
{
memset(F,0,sizeof(F));
memset(G,0,sizeof(G));
G[0][0]=1;
for(int i=1;i<=N;i++)
{
for(int v=0;v<=V;v++)
{
F[i][v]=F[i-1][v]; //默认不加入物品
G[i][v]=G[i-1][v];
if(v>=C[i]) //可以加入的时候考虑一下
{
F[i][v]=max(F[i-1][v],F[i-1][v-C[i]]+W[i]);
if(F[i-1][v-C[i]]+W[i]>F[i-1][v])
{
G[i][v]=G[i-1][v-C[i]];
}
else if(F[i-1][v-C[i]]+W[i]==F[i-1][v])
{
G[i][v]+=G[i-1][v-C[i]];
}
}
}
}
}

求第K优解

基本思想是将每个状态表示成有序队列,将状态转移方程中的max转化成有序队列的合并。\(F[i,v]\)这个有序队列是由\(F[i-1,v]\)\(F[i-1,v-C_i+W_i\)两个有序队列合并得到的。这个两个有序队列各自有自己的前K个最优解,然后两者合并得到当前的最优的K个解。 代码如下,为了节省空间使用了一维的01背包解法。

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
36
37
38
39
40
41
priority_queue mergeTopK(priority_queue a,priority_queue b,int W,int K)
{
priority_queue c;
while (c.size()<K)
{
if(a.top()>b.top()+W)
{
c.push(a.top());
a.pop();
}
else
{
c.push(b.top()+W);
b.pop();
}
}
return c;
}
void ZeroOnePackTopK(int K)
{
priority_queue FQueue[V+1];
for(int i=0;i<=V;i++)
{
for(int j=1;j<=K;j++)
{
FQueue[i].push(0);//数组初始化为K个0
}
}
for(int i=1;i<=N;i++) { for(int v=V;v>=C[i];v--)
{
FQueue[v]=mergeTopK(FQueue[v],FQueue[v-C[i]],W[i],K);
}
}
while(!FQueue[V].empty())//输出最优的K个解
{
cout<<FQueue[V].top()<<" ";
FQueue[V].pop();
}
cout<<endl;
}

参考: 1.《背包问题9讲》,https://github.com/tianyicui/pack