迪三
0%

三.贪心算法

发表于 分类于 Valine：

原创 进阶算法概述

1.算法本质

  • 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
  • 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

2.解题步骤

类似一个一维数组遍历，每一步遍历都能获得局部最优解，每一次只考虑选取一个数据，它满足当时局部最优解。

  • 伪代码

    一般是一个双重循环，第一重循环是总循环，第二重循环是每次循环求局部最优解

    3.例题

其他

  • 贪心算法

贪心算法的本质：从问题的某一个初始解出发，向给定的目标推进。推进的每一步做一个当时看似最佳的贪心选择。不断的将问题规模缩小。并由所有的局部最优选择产生一个全局最优解

  1. 删数问题

从键盘输入一个高精度正整数N(N不超过200位），任意去掉S个数字，把剩下的数字组合成一个新的正整数，次序不变且剩下的数字组成的新数最小。
输入：N（≤200位），S（1≤S≤10）
例如：

输入

51428397

5

输出

123

  • 代码(python)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 命令行输入输出
# 删数问题

print("输入一个整数")
a = input()
print("输入删除的位数")
b = input()
b = int(b)
n = len(a)    
for i in range(b):
    x=len(a)
    for j in range(x):
        if (j+1)<x:
            if a[j] > a[j+1]:
                a = a[:j]+a[j+1:]
                break
        else:
             a = a[:j]
             break

print(a)

首先：N超过200位，肯定要用字符串数组来进行存储。我们知道字符串数组隐含的’\0’作为结束符。当然，我们也可以用strlen()函数来直接计算字符串长度。

第二步，如何删除数字。假定只删除一个数字。如果数字从左到右为顺序增大，显然删除最后一个可以。如果不是顺序增加的。删除递减区间的第一个就行了。这样循环删除s个数字即可完成。

还要注意一点的是，每删除一个数字，就要从这个数组的第一个单元开始重新判断。所以，用当型循环比较合适。每判断到一个可以删除的数，就结束判断。

https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html