前言

之前找了本不错的算法书籍，叫做《趣学算法》，学习了1/5，后面去读源码了，就暂时搁浅了。

之前恒心不足，但是自从拥有了 AI 助手，对 Python 的兴趣持续走高，这种互动式的编程，还挺有趣的。

所以今年有望读完这本书。

我准备延续之前和 AI助手互动式编程的方式，让 AI 实现算法题目，我来反向解析。

贪心算法

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。

——《算法导论》

本文主要围绕"贪心算法"进行题目的解析。

贪心算法，又叫贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。

注意，"在当前"三个字，可以这样理解，贪心算法并不是整体最优考虑，而是在某种意义上的局部最优解。

如果得不到最优解，得到最优解的近似解也是可以的。

最优装载问题

题目描述

这是一个经典的轮船最优装载的题目：

一天，一艘货轮正在装货，这艘货轮的载重量是C，每件货物的重量是。

现在需要装入尽可能多的货物，但是所有的货物总重量不能超过货轮的载重量。

问：最多能装多少件货物？

来活了，AI 助手

功能注释

将题目转换成注释，录入到 py 文件中：

"""
1、假设有一辆轮船正在装货；
2、现在有一组货物需要装上，每个货物的重量为：4,10,7,11,3,5,14,2；
3、装货的限制是，装入的货物重量之和不能超过轮船的载重量30；
4、现在设计一个算法，求出轮船能装入货物的最多的总数量。
:return:
"""

生成代码

在注释下方进行"回车"操作，CodeArts Snap 可以自动生成代码：

def max_goods(weight, goods):
    """
    :param weight: 货物重量
    :param goods: 货物列表
    :return: 最大的货物数量
    """
    if len(goods) == 0:
        return 0
    goods.sort()
    max_weight = 0
    count = 0
    for i in range(len(goods)):
        if max_weight + goods[i] <= weight:
            max_weight = max_weight + goods[i]
            count += 1
    return count

这次的代码十分漂亮，给出了入参和返回的注释。

运行结果

我们来按照入参的注释，定义 goods：

goods = [4,10,7,11,3,5,14,2]

打印最终的结果

print(max_goods(weight, goods))

最优装载和货轮的载重量有关，不同的载重量会有不同的结果。

先来设置的最大载重量为：30，运行代码，得到结果是：5。

我又观察了一下这组货物的特点，发现一个很妙的载重量：31，于是重新设置了一下，运行代码，得到结果是：6。

算法解析

这个算法实现的基本思路如下：

1、先对货物数组 goods 进行了重量大小的排序，得到一个从小到大的顺序数组；

2、for循环货物列表，进行一下处理：

• 每次得到的货物重量增加到 max_weight 里；
• 每次都将 count 的值增加1；
• 直到最后一次需要增加的货物的重量与max_weight的值大于货轮的载重量时，停止循环，此时得到的 count 的值，就是最优装载的数量。

算法复杂度分析

1、时间复杂度：首先调用了 sort 函数进行排序，其平均时间复杂度O(nlogn)，其次 for 语句的时间复杂度为O(n)，因此时间复杂度为O(n+nlogn)。

2、空间复杂度：程序中变量 max_weight、count等占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为O(1)。

算法延展：背包问题

最优装载问题解决完，是不是感觉还挺简单的，这是因为在这个问题里，存在单一维度的对比：货物的重量与货轮载重量的对比。

如果增加对比的维度，又该如何求得最优解呢？

来看一个背包问题。

题目描述

假设小明发现了一个山洞，山洞中有n 种宝物，每种宝物有一定重量 w 和相应的价值 i，背包能力只能装入 m 重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使背包装入的宝物的价值最大呢?

宝物清单

宝物 i	重量 w[i]	价值 v[i]
1	4	3
2	2	8
3	9	18
4	5	6
5	5	8
6	8	20
7	5	5
8	4	6
9	5	7
10	5	15

排序后宝物清单

这次需要选择性价比（价值/重量）高的宝物，所以先来按照性价比对宝物进行排序。

宝物 i	重量 w[i]	价值 v[i]	性价比 p[i]
2	2	8	4
10	5	15	3
6	8	20	2.5
3	9	18	2
5	5	8	1.6
8	4	6	1.5
9	5	7	1.4
4	5	6	1.2
7	5	5	1
1	4	3	0.75

假设背包的最大装入重量 m = 30，求解怎么装入最大价值的宝物？

我们先来手工数一下：

• 2+5 = 7；
• 2+5+8 = 15；
• 2+5+8+9 = 24；
• 2+5+8+9+5 = 29；
• 2+5+8+9+5+4 = 33

好，加到第6个宝物的时候，重量超过了33，所以最多可以装5个，重量分别是2，5，,8，,9，5。

有了前面的经验，我准备自己尝试着实现这个算法，而不是借助 AI 助手（主要是指令还没有写的特别精准）。

实现思路

1、计算每个宝物的性价比；

2、依次选择性价比高的物品放入背包，同时计算目前物品的总重量；

3、当放入背包的物品的总重量大于背包最大装入重量时，停止放入；

4、此时得到的就是可以装入的最大价值的宝物。

算法代码

def max_goods(backage_w, goods_w,goods_v):
    goods_p = []
    best_v = 0
    best_w = 0
    # 如果宝物重量或者宝物价值数组为空，则返回空
    if (len(goods_w) == 0 | len(goods_v) == 0):
        return 0
    # 遍历宝物重量数组，重组数组为二维数组，二维数组中包含性价比的值
    for i in range(len(goods_w)):
        # 性价比 = 价值 / 重量
        item_p = goods_v[i]/goods_w[i]
        q = [goods_w[i], goods_v[i], item_p]
        goods_p.append(q)
    # 排序：根据性价比的值从大到小排序 reverse需为True
    goods_p_sorted = sorted(goods_p, key=lambda x: x[2], reverse=True)
    # 遍历排序后的数组，计算目前物品的总重量，直到物品总重量大于背包可装入的最大重量
    for j in range(len(goods_p_sorted)):
        if(best_w + goods_p_sorted[j][0] <= backage_w):
            # 每次叠加重量
            best_w += goods_p_sorted[j][0]
            # 每次叠加价值
            best_v += goods_p_sorted[j][1]
    print('可装入的最大重量：', best_w)
    print('可装入的最大价值：', best_v)
goods_w = [4,2,9,5,5,8,5,4,5,5]
goods_v = [3,8,18,6,8,20,5,6,7,15]
backage_w = 30
max_goods(backage_w, goods_w, goods_v)

运行结果

最终得到的，可装入的最大重量是 29，可装入的最大价值是 69。

算法延展

来看一下《Python算法设计与分析》中的实现方案：

def backpack_record(n, c, w, v):
    # n物品名称列表，c背包最大载重 w物品重量列表 v物品价值列表
    # 初始化记录表
    backpack_rec = [[0 for i in range(c + 1)] for i in range(len(n) + 1)]
    for i in range(1, len(n)+1):
        for j in range(1, c+1):
            # 使用状态转移函数填写记录表
            if j < w[i - 1]:
                backpack_rec[i][j] = backpack_rec[i - 1][j]
            else:
                backpack_rec[i][j] = max(backpack_rec[i - 1][j], backpack_rec[i - 1][j-w[i - 1]] + v[i - 1])
    return backpack_rec

这个实现方案的主要思想是第 i 个宝物是否被选择了。

背包目前的承重量为j(1≤j≤C)，于是可以把前 i 个物品中能够放进承重量为 j 的背包中的子集分为两种类别：包括第 i 个物品的子集和不包括第 i 个物品的子集。

• 在不包括第i个物品的子集中，最优子集的价值是F(i-1,j)；
• 在包括第i个物品的子集中（j-wi≥0），最优子集是由该物品和前i-1个物品中能够放进承重量为j-wi的背包的最优子集组成。这种最优子集的总价值等于vi+F(i-1,j-wi)。

因此，在前i个物品中，最优解的总价值等于以上两种情况中求得的价值的较大值。

总结

贪心算法小结

1、受前面 AI 自动生成算法的启发，背包问题我也很快找到了实现方案。虽然不是最优方案，但是至少保持了学习的热情。

2、美中不足的是，我的 AI 指令还没有练好。

自动生成代码质量与 prompts

因为我才开始接触 ChatGPT 类工具，且过程也比较零散，所以多了摸索的乐趣，同时也难免走些弯路。

好在笔者加入的技术群较多，总能看到大佬们的分享。我之前一直觉得我的 AI 助手无法理解我的问题，后来才知道有个名词叫做"prompts"，它的意思是 AI 指令。ChatGPT 输出的结果的质量高低与 prompts 高度相关。

所以严格上将，AI 实现的算法并非不够准确，而是我可能要提升我给出的 prompts。

关于 prompts，我再延展一点，上周去参加线下技术大会，大佬给了关于 prompts 的建议，可以利用一些现有的 prompts 框架，实现一个 prompts 输出工具，提升 ChatGPT 输出的结果的质量。

变化着的学习兴趣

无论是算法，还是 Python，我都有些担心自己没有坚持学下去的恒心。

这次因着对 AI 助手的体验兴趣，能够接续之前的学习进度，虽然是不同的方式，但是结果还是挺令人欣慰的。

以一个开放的心态，去拥抱变化，可能会有意想不到的收获。

学习的改良策略

我之前的困扰是：

从头学的时候，知识点感觉上都会了，但是遇到具体问题，不会编程。

这个问题的关键点在于我没有投入一定量练习。实际上我练了几个功能，写的不理想，所以渐渐就不写了。

如果有和我相似情况的开发者，可以参考我接下来的改良策略，以 Python 为例：

• 先找到一本有大量实例的书籍，比如《Python算法设计与分析》；
• 然后依样画葫芦，先让AI帮忙实现某个功能，然后在对照书本中的解决方案，进行代码优化；
• 优化过程中，可以尝试自己实现局部代码。这个过程有两点需要注意的：

• • 第一个，不好担心自己实现的不够完美，首先能得到正确的结果，然后再摸索最优的方案；
  • 遇到不熟悉的知识点，一定要去查清楚，查找的过程也是学习的过程，且有助于活学活用；

• 完成某个章节的代码实践之后，归纳总结这个章节的笔记，尤其自己第一次接触到的。
• 最后，抛开书本，找一个案例，完全的自己编写代码尝试实现。还是那句话，不要担心自己写的代码不够完美。

希望每个开发者都能找到适合自己的学习之路。

最后，祝大家端午安康。