又想到一个不入流的小算法

        周末儿子的火花思维即将到期，火花思维运营人员想让我们续课，但儿子幼小衔接的老师是原北京四中的数学教师，说不推荐火花思维，那我们就不续课了。

        我们在这个平台上还有67730的积分，可以兑换很多商品，但如何保证兑换的商品是我们想要的，并且能够达到兑换之后完全花光这些积分以保证利益最大化，我第一个想法就是背包，贪婪，穷举等解法。

        ChatGPT问了问，都是递归+穷举，还有运行的问题，不符合要求等，弄的我实在不知道prompt应该如何优化了，有擅长的朋友们，可以评论区留言，不胜感谢！

1. 通过app抓包拿到所有商品的信息，包括商品名称 + 价格
2. 因有可能多个商品对应一个价格，所以要将作为价格的key，对应列表元素的value，例如{9900: ["洗面奶", "铅笔盒"]}
3. 写算法

    从研发领域出来已经有快3年了，依然念念不忘动态规划，好吧，直接上代码吧

   def find_closest_combination(initial_amount, price_list, num):
       n = len(price_list)
       
       # 创建一个二维数组来保存状态
       dp = [[0] * (initial_amount + 1) for _ in range(n + 1)]
       
       # 初始化第一行，表示使用0个商品时，无论初始金额多少，都只能得到0
       for i in range(initial_amount + 1):
           dp[0][i] = 0
       
       # 填充dp数组
       for i in range(1, n + 1):
           for j in range(1, initial_amount + 1):
               if price_list[i - 1] <= j:
                   # 当前商品的金额小于等于当前金额，可以选择使用或者不使用
                   dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - price_list[i - 1]] + price_list[i - 1])
               else:
                   # 当前商品的金额大于当前金额，不能选择使用
                   dp[i][j] = dp[i - 1][j]
       
       # 回溯找到最优解
       selected_all_items = []
       # i, j = n, initial_amount
       for x in range((initial_amount + 1) * (n + 1)):
           selected_items = []
           i, j = int(x / (initial_amount + 1)), x % (initial_amount + 1)
           while i > 0 and j > 0:
               if len(selected_items) == 0 or dp[i][j] != dp[i-1][j]:
                   selected_items.append(price_list[i - 1])
                   j -= price_list[i - 1]
               i -= 1
           tmp = sorted(selected_items)
           if len(tmp) > 0 and tmp not in selected_all_items:
               selected_all_items.append(tmp)
       sort_list(selected_all_items)
       return sort_list(selected_all_items)[:num]
    
   # 将结果以desc排序，可以根据个人需求从头取
   def sort_list(lst):
       if len(lst) == 0:
           return lst
       ret = []
       tmp = []
       for itm in lst:
           tmp.append(sum(itm))
       ret = sorted(tmp, reverse=True)
       for itm in lst:
           idx = ret.index(sum(itm))
           ret[idx] = itm
       return ret
    
   if __name__ == "__main__":
       target = 30
       price_list = [5, 10, 12, 13, 15]
       print(find_closest_combination(target, price_list, 2))
   

           其实最开始只是找到了最符合要求的唯一解，后来觉得这样不满足商品是否是我们需要的，最好能给出多一些方案，所以在方法参数中加入阈值参数num。

4. 最后，通过金额取出商品名称组合展示，发给老婆炫耀的时候，老婆说，你是真挺闲的😮‍💨

后来使用微软GPT-4模型，对prompt进行了优化后，AI给出了最后的结果，完全符合要求😂

def find_combinations(price_list, num):
    # initialization
    dp = [set() for _ in range(num+1)]
    dp[0].add(())
    # dynamic programming
    for price in price_list:
        for j in range(num-price, -1, -1):
            for k in dp[j]:
                dp[j+price].add(k + (price,))
    # collect combinations
    combinations = []
    for i in range(num+1):
        for comb in dp[i]:
            combinations.append(comb)
    return combinations