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

(一)    贪心法

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

用贪心法求解的问题一般具有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='')

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏玩转全栈

机器学习-数据清洗(二)

如果接触到我上面的那篇文章,机器学习-入门,应该很清楚本文意欲为何。如果不知道为什么,请阅读一下那篇文章,以便打下基础,ok,废话不多说了,进入正题。

3461
来自专栏机器之心

入门 | 玩转词向量:用fastText预训练向量做个智能小程序

6809
来自专栏MyBlog

J-R.Abrial_FM_ICES2006 阅读笔记

该篇文章简要地概述了用B形式化的两个实际的项目, 主要是说明一种"构造即正确"的思路, 并且分析了其中的困难和优势.

951
来自专栏CreateAMind

以静制动的TensorFlow Fold动态计算图介绍

来源:https://zhuanlan.zhihu.com/p/25216368

1841
来自专栏WOLFRAM

版本11.2——追求极致的极限

2174
来自专栏码神联盟

智能对话 | 使用 Java实现 智能对话机器人 -- 附源码

目前人工智能与深度学习顺应了互联网时代潮流,人机对话已经成为目前人工智能领域中非常热门的处理技术。其中基于深度学习的人机对话交换系统(智能机器人)是人工智能最有...

2.2K2
来自专栏新智元

【干货】谷歌 TensorFlow Fold 以静制动,称霸动态计算图

【新智元导读】谷歌日前推出深度学习动态图计算工具 TensorFlow Fold,可以根据不同结构的输入数据建立动态的计算图,简化训练阶段输入数据的预处理过程,...

3623
来自专栏ATYUN订阅号

在Python中使用NLTK建立一个简单的Chatbot

也许你听说过Duolingo(多邻国):一种流行的语言学习应用程序,它可以通过游戏来练习一种新的语言。由于其创新的外语教学风格,它非常受欢迎。它的思想很简单:每...

6695
来自专栏数说工作室

哈希函数的套路 | 文本分析:大规模文本处理(1)

这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货。 第一篇中,介绍了文本相似度是干什么的; 第二篇,介绍了如何量化两个文本,如何计算余弦相似度,穿...

4778
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最短路算法(附C++代码及算例)

最近被BOSS抽查 运筹学 基本功课, 面对BOSS的突然发问, 机智的小编果断选择了—— 拿 · 出 · 课 · 本 然后BOSS 微微一笑 : “来,实现下...

7818

扫码关注云+社区

领取腾讯云代金券