数据结构学习<四> 背包问题(递归,动态规划)

背包问题是算法中一个常见的问题,其应用场景极广,在很多行业方向都有应用。这里主要使用自顶向下递归和动态规划的思路解决。

动态规划

先来一个简单的例子介绍一下
一个著名的数列斐波那契数列
$$
F(n)=F(n-1)+F(n-2)且F(1)=1,F(2)=1
$$
用代码实现则是

1
2
3
4
5
6
7
8
int Fibona1(int i)//直接递归,复杂度1.618^N
{
if (i < 1)
return 0;
if (1 == i)
return 1;
return Fibona1(i - 1) + Fibona1(i - 2);
}

直接递归算法具有指数时间,其复杂度很高不适合实现。

但是我们发现其中有很多的重复计算,那么就可以依据动态规划的思想,将已经知道的项存下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//使用Know[i]这个数组存已经知道的项
int Fibona2(int i)//复杂度为N
{
int t;
if (Know[i] != 0)
return Know[i];
if (i == 0)
t = 0;
if (1 == i)
t = 1;
if (i > 1)
t = F(i - 1) + F(i - 2);
return Know[i] = t;
}

当然还可以只保存前两项,这就是自底向上的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Fibona3(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
int a1 = 1;
int a2 = 1;
int ans;
for (int i = 3; i <= n; i++)
{
ans = a1 + a2;
a2 = a1;
a1 = ans;
}
return ans;
}

背包问题的提出

一个小偷打劫一个保险箱,发现其中装满了N类不同大小与价值的物品,但小偷只有一个大小为M的背包来装物品,背包问题便是要找出小偷该选的物品组合使其价值最大化。

1
2
3
item A B C D E
size 3 4 7 8 9
val 4 5 10 11 13

例如物品的大小与价值如上表,小偷的背包大小为17,求小偷能带走的物品最大价值。

1
2
3
//例子中的背包问题的两个最优解为24
size(D+E)=17 size(A+C+C)=17
val(D+E)=24 val(A+C+C)=24

对于使用递归来求解背包问题,在上一篇数据结构学习<三> 递归及相关问题中我们提到过要解决一个大问题,我们可以先做一个小事情。所以在这里对于大小为cap的背包,对于可用类型的每一项 i,我们可以把 i 放入背包同时使其他项有最优的打包,来得到一个最优解。

递归的解决

就是假设我们已经找到大小为cap-item[i].size的最优背包,现在在 i 个物品中选一个合适的使价格最大就行了,至于大小为cap-item[i].size的最优背包是怎么样的,这又是规模小一点的背包问题了。

1
2
3
4
5
typedef struct
{
int size;
int val;
}Item;

一个不怎么具有效率的递归解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Item
{
public:
int val;
int size;
};
int knap(int cap,Item * items)//递归的背包问题
{
int i,space,max,t;
for(i=0,max=0;i<N;i++)
{
if((space=cap-item[i].size)>=0)//还有空间装下item[i]
if((t=knap(space)+items[i].val)>max)//如item[i]使当前价值最大
max=t;
}
return max;
}

这种算法的思路简单,代码量少,但是这个算法花费指数时间不具有实用价值。

在上述算中我们发现,在重叠的子问题进行了大量的重复运算,我们可以保存已经计算出的值来使背包算法的代价从指数时间下降到线性时间。
我们改进上一个代码,只需要类似斐波那契数列那样保存所计算的值,然后在需要的时候检索已经保存的值,而不是使用递归调用,对于大小为M的子背包,我们使用maxKnown[M]这个值来保存其最优解。

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
42
43
44
45
int Knap2(int M, Item * items,int * maxKnown,Item * itemKnow)
{
int i, space, max, maxi, t;
maxi = -1;
if (maxKnown[M] != 0)
return maxKnown[M];//如果已知大小为M的max,直接返回
for (i = 4, max = 0; i >= 0; i--)
{
if((space=M-items[i].size)>=0)
if ((t = Knap2(space,items,maxKnown,itemKnow) + items[i].val) >= max)
{
max = t;
maxi = i;
}
}
//itemKnow[M]为当背包大小为M时要最有解会有的物品,
//此时itemKnow[M-itemKnow[M].size]为M-itemKnow[M].size这么大的包里最有解会有的物品,
//这样就可以找出最优解组合
//maxKnown[M]保存的是当包大小为M时的最优解,但是这个解和最初的M大小有关?
maxKnown[M] = max; itemKnow[M] = items[maxi];
return max;
}
//test.cpp
int main(void)
{
Item items[5];
items[0].size = 3;
items[0].val = 4;
items[1].size = 4;
items[1].val = 5;
items[2].size = 7;
items[2].val = 10;
items[3].size = 8;
items[3].val = 11;
items[4].size = 9;
items[4].val = 13;
int ans = Knap(17, items);
Item itemKnown[18] = { 0 };
int maxKnown[18] = { 0 };
int ans2 = Knap2(17, items,maxKnown,itemKnown);
return 0;
}