python从入门到马上不行了

一.贪心算法二.最优装载问题1.问题描述2.算法设计3.代码实现 二.教室调度问题1.问题描述2.算法设计 三.背包问题1.问题描述2.算法设计3.代码实现

一.贪心算法

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

二.最优装载问题

1.问题描述

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

2.算法设计

3.代码实现

antique = [4, 10, 7, 11, 3, 5, 14, 2] def max_ans(antique): antique_sort = sorted(antique) ans, tmp = 0, 0 ship = [] for item in antique_sort: tmp += item if tmp <= 30: ans += 1 ship.append(item) print('装载古董数量：', ans) print('装载的古董：', ship) max_ans(antique)

二.教室调度问题

1.问题描述

2.算法设计

你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？ 具体做法如下： (1) 选出结束最早的课，它就是要在这间教室上的第一堂课。 (2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要在这间教室上的第二堂课。 重复这样做就能找出答案！ 贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。

三.背包问题

1.问题描述

2.算法设计

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

3.代码实现

datas = [[4, 3], [3, 8], [9, 18], [11, 30], [5, 8], [3, 6], [4, 13], [3, 9]] m = 30 w = 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] <= m: w += data[1] m -= data[0] else: w += data[2]*m break print('总价值', w)