vlambda博客
学习文章列表

大家好，我是北海。今天来看一道贪心算法的题目。（题目与实现取自LeetCode）

给你数字k，请你返回和为k的斐波那契数字的最少数目，其中每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

F1 = 1

F2 = 1

Fn = Fn-1 + Fn-2 ， 其中 n > 2 。

数据保证对于给定的 k ，一定能找到可行解。

 
   
   
 

  
    
    
  
 
   
 
   
 
   
 
   
 
   
 
  
  
    
    
  
示例：输入：k = 7输出：2 解释：斐波那契数字为：1，1，2，3，5，8，13，……对于 k = 7 ，我们可以得到 2 + 5 = 7 。
 
   
   
 

1、贪心算法的核心思想，就是求解问题时，选择当前看来最好的选择。

2、即不考虑整体最优，每一步得到的是当前局部最优解。

3、如果问题具有最优子结构性质，那么贪心算法最终能求得全局最优。

“最优子结构”是指一个问题的最优解包含其子问题的最优解。

例如：从北京到广东的最短路径，假设沿途经过了南京，那么这条最短路径里包括了从南京到广东的最短路径。

反例：总分第一的人，单科不一定是第一，所以“根据各科考试分数评选年级第一”这个问题就不具备最优子结构，不能使用贪心算法。

思路：

1、求出所有不超过k的斐波那契数

2、基于贪心算法思想，每次选取小于等于k的最大斐波那契数

3、将k减去该斐波那契数字

4、重复步骤2和3，直到k变为0，此时选取的斐波那契数字满足和为k且数目最少

class GreedAlgorithm:  # 创建类 def greed(self, k: int) -> int: # 定义函数        g = [1, 1]    # 初始化斐波那契数列 # 下面的while循环实现步骤1        while g[-1] < k:  # f[-1]是指数组f中倒数第一个数            g.append(f[-1] + f[-2])  # 根据斐波那契数列定义，添加下一个斐波那契数        ans, i = 0, len(g) - 1       # 下面的while循环实现步骤2，3，4 while k:            if k >= g[i]:    # 实现步骤2，选取小于等于k的最大斐波那契数                k -= g[i]    # 实现步骤3，将k减去该斐波那契数字 ans += 1 # 计数 i -= 1        return ans           # 最后计数值就是“和为k的斐波那契数字的最少数目”

在数学上可以证明，只有每次不超过k的最大斐波那契数字，才能使得选取的斐波那契数字满足和为k且数目最少。

这也是能够使用贪心算法的前提：具有最优子结构。

因此在数模竞赛中，如果你无法证明或者查找资料确定该问题具有最优子结构的话，不要轻易使用贪心算法！

注意是只要找到资料确定即可，无需在比赛论文中写出证明过程。

喜欢的话点击右下角的“赞”和“在看”，并分享给更多人~

-----------------------------------

回复 “群”，获得交流群群号，课件在群文件

回复“最新资料”，免费领取超全数模资料

回复“入门”，教你0基础小白入门数学建模