贪心算法实例：将n个短长不一的整数拼成一个最大整数——算法学习笔记

• My CSDN主页、My HOT博、My Python 学习个人备忘录
• 好文力荐、 老齐教室

  自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
            —— 华罗庚

这是我参加“14天阅读挑战赛”第二周第一篇

点击查看“14天阅读挑战赛”详情

今日学习《趣学算法第二版》内容：

2.1 [贪心算法基础]
2.1.1 [贪心算法本质]
2.1.2 [贪亦有道]
2.1.1 [问题分析]
 a、贪心选择
 b、最优子结构
2.1.3 [贪心算法秘籍]

 a、贪心策略，根据求解目标的不同，贪心策略也不同。
 b、求解过程，根据贪心策略，一步步得到最优解。

  贪心算法个人学习理解，最大的难点在于制定贪心策略。贪心策略不当，可能导致问题的解不是最优或无限逼近最优；甚至是让问题不适用贪心算法解答。

题目

［最大整数］设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数

题目分析
  一个整数，高位数字大即大。要把几个整数拼成最大的整数，就得把最高位数字大的拼在前面。基于这直接把数字接最高位数字排序，最后直接拼接输出就好。出于最后输出拼接方便，先把数字转成字符。

    nums.sort(key=lambda x: x[0], reverse=True)

  用list.sort方法对n个整数排逆序(reverse参数为True)。得检验检验，贪心算法策略得检验无误才可使用。

  很显然，第一组“63 6 5 6”，出了“意外”。66635比63665更大，贪心策略还需改进。只考虑每个整数的首位，还有首位相同的情况，则需第二位来决断。整数数位短长不一，也不可以直接以整数较大小。经观察，首位相同，第二位大的就排前，但如65 6这样子的两个整数，以第二数位定短长的策略失效。那，此问题是不是不适用贪心算法？不忙定论，先修正贪心策略试试。看来用单行lambda匿名函数制定的排序规则还太简陋，得重新定制。

  很花费了些工夫打磨出了自己的比较“大小”的代码，经反复试炼，好像“没毛病”。她的“诞生”，另作笔记记录。(点击此处跳转查看详情])

代码

def isbig(num, num2):''' 判定两个整数顺序拼接出最大整数 '''a, b = str(num), str(num2)if (n1 := len(a)) > (n2 := len(b)):b += b[-1]*(n1-n2)else:a += a[-1]*(n2-n1)if a == b: #拼成数位一致后的比较。return Truefor i in range(len(a)):if int(a[i]) > int(b[i]):return Trueelif int(a[i]) < int(b[i]):return False

用“冒泡”定制mysort

def mysort(nums):''' 按自定规则冒泡 '''for i in range(len(nums)-1, 0, -1):n = len(nums)-1while n:if not isbig(nums[n-1], nums[n]):nums[n-1], nums[n] = nums[n], nums[n-1]n -= 1

  刀已磨快！那就上山砍柴呗😄那就先用出前面出意外“ 63 6 5 6 ”祭刀！👀

代码

if __name__ == '__main__':nums = [63, 6, 5, 6]print(f"{len(nums):3}个整数：", end='')print(*nums)mysort(nums) # 调用“冒泡”逆序。print(f"排逆序：", end='')print(*nums)print(f"拼成最大整数：{''.join(map(str, nums))}")

OK✌
  这就对了！“ 66635 ”，最大的整数。🤗🤗再用题目中的例子数组炼炼。

依旧OK✌👀😁😁😁

  多用些数组来炼炼，检证一下。自己写数组，难得整。😣代码对重复的简单琐事不嫌麻烦，请她上场。随机任意长短整数数组皆可定制，个数n，长度默认1~3位亦可自行设定。

代码

def random_nums(n, f=1, b=3):''' 随机数列生成，n数列元素，k每数字最大位数 '''from random import choices, shuffledigits = list('0987654321')tem = []position = list(range(f, b+1))for i in range(n):shuffle(position)k = choices(position, k=1)while True:shuffle(digits)num = choices(digits, k=k[0])if num[0] != '0':breaktem.append(int(''.join(num)))return tem

工作代码

if __name__ == '__main__':nums =  list(map(str, random_nums(6, 1, 3)))print(f"{len(nums):3}个整数：", end='')print(*nums)mysort(nums)print(f"排逆序：", end='')print(*nums)print(f"拼成最大整数：{''.join(map(str, nums))}")

试炼效果截屏图片

  全部检证数组，成功拼接出最大整数！这小小的成功，虽然让“基础不牢”的我绞尽脑汁，但还是收获了一份满满的喜悦。虽然看起来算法丑且繁，也许以后，我可以优化呢。
  虽然探寻贪心策略之路有些艰辛，但让有人怀疑不可以用贪心算法解的这道小题，用贪心算法出解，也是欣慰。

mypycolor完整源码(源码较长，点此跳过源码)

#!/sur/bin/nve python
# coding: utf-8'''Author：梦幻精灵_cqdate：2022-10-24'''def random_nums(n, f=1, b=3):''' 随机数列生成，n数列元素，k每数字最大位数 '''from random import choices, shuffledigits = list('0987654321')tem = []position = list(range(f, b+1))for i in range(n):shuffle(position)k = choices(position, k=1)while True:shuffle(digits)num = choices(digits, k=k[0])if num[0] != '0':breaktem.append(int(''.join(num)))return temdef isbig(num, num2):''' 判定两个整数顺序拼接出最大整数 '''a, b = str(num), str(num2)if (n1 := len(a)) > (n2 := len(b)):b += b[-1]*(n1-n2)else:a += a[-1]*(n2-n1)for i in range(len(a)):if int(a[i]) > int(b[i]):return Trueelif int(a[i]) < int(b[i]):return Falsedef mysort(nums):''' 按自定规则冒泡 '''for i in range(len(nums)-1, 0, -1):n = len(nums)-1while n:if not isbig(nums[n-1], nums[n]):nums[n-1], nums[n] = nums[n], nums[n-1]n -= 1if __name__ == '__main__':nums =  list(map(str, random_nums(6, 1, 3)))nums = [13, 312, 343]nums = [7, 13, 4, 246]#nums = [63, 6, 5, 6]m, n = 44, 44#input(f"{m}, {n}, is {isbig(m, n)}")print(f"{len(nums):3}个整数：", end='')print(*nums)mysort(nums)print(f"排逆序：", end='')print(*nums)print(f"拼成最大整数：{''.join(map(str, nums))}")