算法学习笔记(二):贪心算法

2018-06-18 03:01:46来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

(一)    贪心法

贪心法在解决问题的策略上是根据当前已有的信息做出选择,不管将来有什么结果,这个选择都不会改变。换言之,贪心法并不是从整体最优考虑,它所做出的选择只是某种意义上的局部最优。

用贪心法求解的问题一般具有2个重要的性质:

(1)   最优子结构:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构。问题的最优子结构是该问题能采用贪心法求解的关键性质。

(2)   贪心选择性质:指问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来得到。这也是贪心法和动态规划法的主要区别。

(二)    示例1

设有0,1,…,n-1个物品,体积分别为v0,v1,…,vn-1 ,将这些物品装入容量都为v的若干个箱子中,不同的装箱方案所需要的箱子数目可能不同,装箱问题要求使装尽这n种物品的箱子数最少。

约定:

(1)   物品体积不超过箱子容量。

(2)   现有的箱子足以装入所有物品

(3)   物品不能拆分

算法描述:

输入物品列表信息

输入箱子列表信息

将物品列表按体积降序排序(从大到小)

    while 还有物品未装入箱子:

        if 物品体积 <= 箱子容量:

             将物品装入箱子

             更新箱子容量

             物品列表中移除已经装入箱子的物品

         else:(如果当前箱子不足以装入物品)

              获取下一个箱子的索引

 1 import random
 2 import operator
 3 #物品类
 4 class goods():
 5     def __init__(self,goods_name,goods_v):
 6         self.goods_name = goods_name #物品名称
 7         self.goods_v = goods_v   #物品体积
 8 #箱子类
 9 class box():
10     def __init__(self,box_name):
11         self.box_name = box_name #箱子名称
12         self.box_v = 50  #箱子容量
13 
14 #贪心算法实现,goods_list:物品列表  box_list:箱子列表
15 def greedy(goods_list,box_list):
16     cmpfun = operator.attrgetter('goods_v')
17     goods_list.sort(key=cmpfun, reverse=True)  # 将物品列表按体积降序排序
18     i = 0 #物品列表索引(下标)
19     j = 0 #箱子列表索引(下标)
20     box_count = 0 #初始化箱子使用数量
21     while goods_list:
22         if goods_list[i].goods_v <= box_list[j].box_v:
23             print('将物品:'+str(goods_list[i].goods_name)+"    装入箱子:", box_list[j].box_name)
24             #更新箱子容量
25             box_list[j].box_v = box_list[j].box_v - goods_list[i].goods_v
26             j = 0
27             del goods_list[i] #从物品列表中移除已经装入箱子的物品
28         else:
29             j += 1
30             if box_count < j :
31                 box_count = j
32      # 因为索引从0开始的,所以这里+1后得到箱子使用数量
33     print('最终使用箱子数:',box_count+1)
34     return box_list
35 
36 goods_list = []
37 #初始化10个物品
38 for i in range(10):
39     goods_name = "物品%s"%i
40     goods_v = random.randint(1,50)
41     goods_list.append(goods(goods_name,goods_v))
42 
43 box_list = []
44 #初始化10个箱子
45 for i in range(10):
46     box_name = "箱子%s"%i
47     box_list.append(box(box_name))
48 
49 box = greedy(goods_list,box_list)
50 print("箱子使用情况:")
51 for i in box:
52     print(i.box_name + '  剩余容量:' + str(i.box_v))

 

(三)    示例2(0-1背包问题)

现在商店有0,1,…,n件商品,体积分别为V0,V1,…,Vn ,价值分别为P0,P1,…,Pn ,假设背包容量为V,现在要求使背包装入商品的价值最大化。

约定:

(1)   背包不足以装入所有物品。

(2)   每个商品,要么完整装入,要么放弃该商品,不能只装入商品的一部分。

算法描述:

    输入商品列表信息

    输入背包容量

    将商品列表按单位价值降序排序(就是性价比,例如:每斤值多少钱)

    while 还有商品未装入背包(或者未排除):

        if  商品体积小等于背包剩余容量:

              将商品装入背包

              更新背包剩余容量

              在商品列表中移除已经装入背包的商品

        else:(如果背包剩余容量不足以装入商品)

              在商品列表中移除不能装入背包的商品

 1 import random
 2 import operator
 3 #商品类
 4 class goods():
 5     def __init__(self,goods_name,goods_v,goods_p):
 6         self.goods_name = goods_name #商品名称
 7         self.goods_v = goods_v   #商品体积
 8         self.goods_p = goods_p   #商品总价值
 9         self.value = self.goods_p/self.goods_v #商品单位价值
10 
11 #贪心算法实现,goods_list:商品列表 V:背包剩余容量 result_list:存放最终装入背包的商品
12 def greedy(goods_list,V,result_list):
13     cmpfun = operator.attrgetter('value')
14     goods_list.sort(key=cmpfun,reverse=True) #将商品列表按单位价值降序排序
15     #打印排序后的所有商品信息,这里为方便看效果,实际可以去掉这个
16     for goods in goods_list:
17         print(goods.goods_name +"  体积:"+str(goods.goods_v)+"  价值:" + str(goods.goods_p) + "  单位价值:" +str(goods.value))
18     while goods_list and V > 0:
19         i = 0
20         #如果商品体积小等于背包容量
21         if goods_list[i].goods_v <= V:
22             #将商品放入背包
23             result_list.append(goods_list[i])
24             #更新背包剩余容量
25             V = V - goods_list[i].goods_v
26             #在列表中删除该商品
27             del goods_list[i]
28         else:
29             del goods_list[i]
30     print('背包剩余空间',V)
31     return result_list
32 
33 
34 V = 100 #初始化背包容量
35 goods_list = []
36 #初始化1000个商品
37 for i in range(1000):
38     goods_name = "商品%s"%i
39     goods_v = random.randint(1,100)
40     goods_p = random.randint(1,100)
41     goods_list.append(goods(goods_name,goods_v,goods_p))
42 result_list = []
43 result = greedy(goods_list,V,result_list)
44 print("最终装入背包的商品:",end='')
45 for i in result:
46     print(i.goods_name + ",",end='')

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Python字符串和编码

下一篇:Python数据类型之list和tuple