动态规划之 0-1背包问题及改进

有N件物品和一个容量为V的背包。第i件物品的重量是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。在选择装入背包的物品时,对于每种物品i,只能选择装包或不装包,不能装入多次,也不能部分装入,因此成为0-1背包问题。

形式化描述为:给定n个物品,背包容量C >0,重量 第i件物品的重量w[i]>0, 价值v[i] >0 , 1≤i≤n.要求找一n元向量(X1,X2,…,Xn,), Xi∈{0,1}, 使得 ∑(w[i] * Xi) ≤C,且∑ v[i] * Xi达最大.即一个特殊的整数规划问题。

数学描述为:                                          

求解最优值:

设最优值m(i,j)为背包容量为j、可选择物品为i,i+1,……,n时的最优值(装入包的最大价值)。所以原问题的解为m(1,C)

将原问题分解为其子结构来求解。要求原问题的解m(1,C),可从m(n,C),m(n-1,C),m(n-2,C).....来依次求解,即可装包物品分别为(物品n)、(物品n-1,n)、(物品n-2,n-1,n)、……、(物品1,物品2,……物品n-1,物品n)。最后求出的值即为最优值m(1,C)。

若求m(i,j),此时已经求出m(i+1,j),即第i+1个物品放入和不放入时这二者的最大值。

对于此时背包剩余容量 j=0,1,2,3……C,分两种情况:

(1)当 w[i] > j ,即第i个物品重量大于背包容量j时,m(i,j)=m(i+1,j)

(2)当 w[i] <= j ,即第i个物品重量不大于背包容量j时,这时要判断物品i放入和不放入对m的影响。

        若不放入物品i,则此时m(i,j)=m(i+1,j)

        若放入物品i,此时背包剩余容量为 j-w[i],在子结构中已求出当容量k=0,1,2……C 时的最优值m(i+1,k)。所以此时m(i,j)=m(i+1,j-w[i])+v[i]。

        取上述二者的最大值,即m(i,j) = max{ m(i+1,j),m(i+1,j-w[i])+v[i] }

总结得出状态转移方程为:

该算法的python代码实现:

 1 # 0-1背包问题
 2 __author__ = 'ice'
 3 
 4 
 5 # 背包容量0~capacity,不是0~capacity-1
 6 def knapsack(weight, value, capacity):
 7     if len(weight) != len(value):
 8         print("parameter err!")
 9         return
10     obj_num = len(weight)
11     result = [[] for x in range(obj_num)]
12     divide = min(weight[-1], capacity)
13     result[-1] = [0 for x in range(divide)]
14     result[-1].extend(value[-1] for x in range(divide, capacity + 1))
15     for i in reversed(list(range(1, obj_num - 1))):
16         divide = min(weight[i], capacity)
17         for j in range(divide):
18             result[i].append(result[i + 1][j])
19         for j in range(divide, capacity + 1):
20             result[i].append(max(result[i + 1][j], result[i + 1][j - weight[i]] + value[i]))
21 
22     result[0] = {capacity: result[1][capacity]}
23     if weight[0] <= capacity:
24         result[0][capacity] = max(result[1][capacity], result[1][capacity - weight[0]] + value[0])
25 
26     vector = [0 for x in range(obj_num)]
27     capacity_temp = capacity
28     for i in range(obj_num - 1):
29         if result[i][capacity_temp] != result[i + 1][capacity_temp]:
30             vector[i] = 1
31             capacity_temp -= weight[i]
32 
33     if capacity_temp == 0:
34         vector[-1] = 0
35     else:
36         vector[-1] = 1
37 
38     return {'total_value': result[0][capacity], 'select': vector}

但是,但是!!该算法有两个明显的缺点:1,基于上述代码,因为数组索引的需要,要求所给物品重量为整数。2,当背包容量C很大时,算法所需计算时间较多。当C>2^n时,需要Ω(n*2^n)计算时间。

所以,所以!!改进算法如下:

对于函数m(i,j)的值,当i确定,j为自变量时,是单调不减的跳跃式增长,如图所示。而这些跳跃点取决于在(物品i,物品i+1,……物品n)中选择放入哪些物品使得在放入重量小于容量 j (0<=j<=C)的情况下m取得最大值。对于每一个确定的i值,都有一个对应的跳跃点集Pi={ ( j, m(i,j) ),……}。j始终小于等于C

(1)开始求解时,先求Pi,初始时Pn+1={(0,0)},i=n+1,由此按下列步骤计算Pi-1,Pi-2……P1,即Pn,Pn-1,……P1

(2)求Qi,利用Pi求出m(i,j-w[i-1])+v[i-1],即Pi当放入物品i-1后的变化后的跳跃点集Qi={ ( j+w[i-1], m(i,j)+v[i-1] ),……},在函数图像上表现为所有跳跃点横轴坐标右移w[i-1],纵轴坐标上移v[i-1]。

(3)求Pi-1,即求Pi∪Qi然后再去掉受控跳跃点后的点集。此处有个受控跳跃点的概念:若点(a,b),(c,d)∈Pi∪Qi,且a<=c,b>d,则(c,d)受控于(a,b),所以(c,d)∉Pi-1。去掉受控跳跃点,是为了求得在物品i-1放入后m较大的点,即 使m取最优值的跳跃点。

由此计算得出Pn,Pn-1,……,P1。求得P1的最后那个跳跃点即为所求的最优值m(1,C)。

举个栗子:

n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。跳跃点的计算过程如下:

初始时p[6]={(0,0)}

因此,q[6]=p[6]⊕(w[5],v[5])={(4,6)}

p[5]={(0,0),(4,6)}

q[5]=p[5]⊕(w[4],v[4])={(5,4),(9,10)}

p[4]={(0,0),(4,6),(9,10)}  p[5]与q[5]的并集p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后,得到p[4]

q[4]=p[4]⊕(6,5)={(6,5),(10,11)}

p[3]={(0,0),(4,6),(9,10),(10,11)}

q[3]=p[3]⊕(2,3)={(2,3),(6,9)}

p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}

q[2]=p[2]⊕(2,6)={(2,6),(4,9),(6,12),(8,15)}

p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}

p[1]的最后的那个跳跃点(8,15)即为所求的最优值,m(1,C)=15

最后,python代码的实现:

 1 class Point:
 2     def __init__(self, x, y):
 3         self.x = x
 4         self.y = y
 5 
 6 
 7 # 0-1背包问题 改进
 8 def knapsack_improve(weight, value, capacity):
 9     if len(weight) != len(value):
10         print("parameter err!")
11         return
12     obj_num = len(weight)
13     jump_points_p = [[] for x in range(obj_num)]
14     jump_points_q = [[] for x in range(obj_num)]
15     jump_points_p.append([Point(0, 0)])
16     jump_points_q.append([Point(weight[obj_num - 1], value[obj_num - 1])])
17     for i in reversed(list(range(1, obj_num))):
18         jump_points_p[i] = merge_points(jump_points_p[i + 1], jump_points_q[i + 1])
19         jump_points_q[i] = [Point(point.x + weight[i - 1], point.y + value[i - 1]) for point in jump_points_p[i] if
20                             point.x + weight[i - 1] <= capacity]
21     result = merge_points(jump_points_p[1], jump_points_q[1])
22     return result
23 
24 
25 def merge_points(points_x, points_y):
26     x_len = len(points_x)
27     y_len = len(points_y)
28     merged_points = []
29     i = j = 0
30     while True:
31         if i == x_len or j == y_len:
32             break
33         if points_x[i].x < points_y[j].x:
34             merged_points.append(points_x[i])
35             if points_x[i].y >= points_y[j].y:
36                 j += 1
37             i += 1
38         else:
39             merged_points.append(points_y[j])
40             if points_y[j].y >= points_x[i].y:
41                 i += 1
42             j += 1
43     while i < x_len:
44         if points_x[i].x > merged_points[-1].x and points_x[i].y > merged_points[-1].y:
45             merged_points.append(points_x[i])
46         i += 1
47     while j < y_len:
48         if points_y[j].x > merged_points[-1].x and points_y[j].y > merged_points[-1].y:
49             merged_points.append(points_y[j])
50         j += 1
51     return merged_points
52 
53 
54 result = knapsack_improve([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10)
55 print()
56 for point in result:
57     print('(' + str(point.x) + ',' + str(point.y) + ')', end=' ')
58 
59 #(0,0) (2,6) (4,9) (6,12) (8,15) 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(六)——巧用数学符号

【AI100 导读】欢迎阅读《数学不好,也可以学好人工智能》系列的第六篇文章。如果你错过了之前的五部分,一定记得把它们找出来看一下!这篇文章作者会帮你学习数学符...

43180
来自专栏余林丰

初学数据挖掘——相似性度量(二)

  上一篇中介绍了四个算法,并用四个算法分别计算了两个人的相似度。这篇就来讲讲相似性算法在实际当中怎么用。第一:将指定的人与其他人作相似性比较,并从高到低进行排...

26960
来自专栏奇点大数据

遗传算法(2)

在遗传算法中我们再举一个求极大值的例子。这种例子也是比较多见的,只要我们把一些数据关系描述成函数之后就会有一些求极大值或者极小值的问题。 其实极大值和极小值是一...

387120
来自专栏C语言及其他语言

【每日一题】问题 1429[蓝桥杯][历届试题]兰顿蚂蚁

题目描述 ? 兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。 平面上的正方形格子被填上黑色或白色。在其中一格正方形内有...

30060
来自专栏机器学习算法原理与实践

贝叶斯个性化排序(BPR)算法小结

    在矩阵分解在协同过滤推荐算法中的应用中,我们讨论过像funkSVD之类的矩阵分解方法如何用于推荐。今天我们讲另一种在实际产品中用的比较多的推荐算法:贝叶...

38230
来自专栏UAI人工智能

深度学习入门教程 第一讲

19130
来自专栏窗户

怀念Galois

  我的第一篇谈到具体学科的博客,还是献给我最钟爱的数学。   个人比较喜欢离散数学,并非因为曲高和寡,而是因为数学分析、概率论、拓扑学、泛函之类的高手实在太多...

20950
来自专栏AI研习社

文本分类又来了,用 Scikit-Learn 解决多类文本分类问题

在商业领域有很多文本分类的应用,比如新闻故事通常由主题来分类;内容或产品常常被打上标签;基于如何在线谈论产品或品牌,用户被分成支持者等等。

19610
来自专栏计算机视觉战队

利用深度学习消去反光

越来越接近毕业季了,相信很多同学都结束了论文的撰写以及论文审批,现在就坐等着毕业论文答辩和毕业典礼了!其实我也是这样的一个状态,但是期间大Boss还是会安排很多...

18710
来自专栏水击三千

经纬度转换-----度分秒以及经纬度和米

经纬度互换 度(DDD):E 108.90593度    N 34.21630度     如何将度(DDD):: 108.90593度换算成度分秒(DMS)东经...

72870

扫码关注云+社区

领取腾讯云代金券