记录生活中的点点滴滴

0%

贪心算法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

基本思路

  1. 建立数学模型来描述问题。

  2. 把求解的问题分成若干个子问题。

  3. 对每一子问题求解,得到子问题的局部最优解。

  4. 把子问题的解局部最优解合成原来解问题的一个解。

存在问题

  1. 不能保证求得的最后解是最佳的;

  2. 不能用来求最大或最小解问题;

  3. 只能求满足某些约束条件的可行解的范围。

求解过程

1
2
3
4
5
6
7
从问题的某一初始解出发;

while 能朝给定总目标前进一步 do

求出可行解的一个解元素;

由所有解元素组合成问题的一个可行解。

贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,换句话说,当考虑做何种选择的时候,我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。贪心算法以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。

举个栗子

[找零钱问题] 假如老板要找给我99分钱,他有上面的面值分别为25,10,5,1的硬币数,为了找给我最少的硬币数,那么他是不是该这样找呢,先看看该找多少个25分的,诶99/25=3,好像是3个,要是4个的话,我们还得再给老板一个1分的,我不干,那么老板只能给我3个25分的拉,由于还少给我24,所以还得给我2个10分的和4个1分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@Test
public void testGiveMoney() {
//找零钱
int[] m = {25, 10, 5, 1};
int target = 99;
int[] results = giveMoney(m, target);
System.out.println(target + "的找钱方案:");
for (int i = 0; i < results.length; i++) {
System.out.println(results[i] + "枚" + m[i] + "面值");
}
}

public int[] giveMoney(int[] m, int target) {
int len = m.length;
int[] res = new int[len];//要返回的数值
for (int i = 0; i < len; i++) {
res[i] = target / m[i];
target = target % m[i];
}
return res;
}

如果一个货币系统有三种币值,面值分别为一角、五分和一分,求最小找币数时,可以用贪心法求解;如果将这三种币值改为一角一分、五分和一分,就不能使用贪心法求解。例如136块钱,现在有1,5,11张纸币,然后我还告诉你每张纸币的个数足够,问:至少需要多少张可以凑出136块钱,输出的居然是16,不是14吗?(11张11,3张5)

用贪心法解题很方便,但它的适用范围很小,判断一个问题是否适合用贪心法求解,目前还没有一个通用的方法,这需要凭个人的经验来判断。

[最大整数]设有n个正整数,0将它们连接成一排,组成一个最大的多位整数。
例如:n=3时,3个整数13,312,343,连成的最大整数为34331213。
又如:n=4时,4个整数7,13,4,246,连成的最大整数为7424613。
输入:n
N个数
输出:连成的多位数
算法分析:此题很容易想到使用贪心法,很多同学把整数按从大到小的顺序连接起来,测试题目的例子也都符合,但最后测试的结果却不全对。按这种标准,我们很容易找到反例:12,121应该组成12121而非12112,那么是不是相互包含的时候就从小到大呢?也不一定,如12,123就是12312而非12123,这种情况就有很多种了。是不是此题不能用贪心法呢?
其实此题可以用贪心法来求解,只是刚才的标准不对,正确的标准是:先把整数转换成字符串,然后在比较a+b和b+a,如果a+b>=b+a,就把a排在b的前面,反之则把a排在b的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 @Test
public void testMaxNum() {
//有n个正整数,将它们连接成一排,组成一个最大的多位整数
//12112错误
//12121正解
// int[] nums = {12, 121};
int[] nums = {12, 7, 9, 3, 123};
String result = maxNum(nums);
System.out.println("组成最大整数:" + result);
}

/**
* 根据给定的整数组成最大的多位数
* @param nums
*/
public String maxNum(int[] nums) {
String result = "";
int len = nums.length;
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
String s1 = nums[i] + "";
String s2 = nums[j] + "";
if((s2+s1).compareTo(s1+s2)>0){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
}
for (int i = 0; i < len; i++) {
result += nums[i];
}
return result;
}

贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。