贪心算法（Python实现）

贪心算法（Greedy Algorithme）含义：

在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

下面我们通过具体的问题去应用贪心算法。

最优装载问题

问题描述：

有一天海盗们截获了一艘装满各种各样古董的货船，每一件都价值连城，一旦打碎就是去了价值， 海盗船载重量为C，每件固定的重量为wi，海盗们该如何尽可能装载最多数量的古董呢？ 

古董重量清单：

重量W[i]41071135142

 算法设计：

1. 船载重量固定为C，只要每次选择重量最小的古董，直到不能再装为止，这样装载的古董数量最大，这就是贪心策略；

2. 把古董按重量从小到大排序，根据策略选出尽可能多的古董。

用Python实现最优装载问题，代码如下：

def max_ans(antique): anti_sort = sorted(antique) # 对重量排序 C = int(input("请输入海盗船所能装载的最大容量：")) ans, tmp = 0, 0 # ans记录装载古董数量，tmp记录装载古董重量 ship = [] # 记录装载的古董 for a in anti_sort: tmp += a if tmp <= C: ans += 1 ship.append(a) print("装载古董的数量：", ans) print("装载的古董", ship)

 对其进行测试，测试代码如下：

if __name__ == '__main__': antique = [4, 10, 7, 11, 3, 5, 14, 2] max_ans(antique)

 测试结果输出为：

---

背包问题 

 问题描述：

假设山洞中有n种宝物，每种宝物有一定重量w和相应的价值v，毛驴运载能力 一种宝物只能拿一样，宝物可分割。怎样才能使毛驴运走宝物的价值最大呢？

问题分析：

可以尝试三种贪心策略：

每次挑选价值最大的装东西入背包；每次挑选最重的东西；每次选取单位重量价值最大的东西。

算法设计：

1. 计算出每件宝物的性价比，按照从高到低排序；

2. 根据贪心策略，按性价比从大到小选取宝物，直到达到毛驴的运载能力。每次选择宝物后判断是否小于m，如果不小于则取走宝物的一部分，程序结束。 

用Python实现背包问题，代码如下：

# datas中每个元素代表一个古董，每个列表第一个元素代表古董重量，第二个元素代表古董价值 datas = [ [4, 3], [2, 8], [9, 18], [5, 6], [5, 8], [8, 20], [5, 5], [4, 6], [5, 7], [5, 15] ] donkey = 30 # 毛驴运载能力 get_price = 0 # 获取的总价值 for i in range(len(datas)): price = datas[i][1] / datas[i][0] datas[i].append(price) datas.sort(key=lambda data : data[2], reverse=True) # 按性价比排序 # 按性价比从大到小选取宝物，直到达到毛驴的运载能力 for data in datas: if data[0] <= donkey: get_price += data[1] donkey -= data[0] else: get_price += data[2] * donkey # 取走宝物的一部分 break print("总价值：", get_price)

输出结果如下：