贪心算法解析示例

贪心算法解析示例

定义

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解

贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

思想

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行,根据某个优化测度,每一步都要确保能获得局部最优解。每一步只考虑一个数据,他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时,就不把该数据添加到部分解中,直到把所有数据枚举完,或者不能再添加算法停止

过程

  • 建立数学模型来描述问题;
  • 把求解的问题分成若干个子问题;
  • 对每一子问题求解,得到子问题的局部最优解;
  • 把子问题的解局部最优解合成原来解问题的一个解。

示例

假设山洞中有 n 种宝物,每种宝物有一定重量 w 和相应的价值 v,毛驴运载能力有限,
只能运走 m 重量的宝物,一种宝物只能拿一样,宝物可以分割。那么怎么才能使毛驴运走宝
物的价值最大呢?
尝试贪心策略:
(1)每次挑选价值最大的宝物装入背包,得到的结果是否最优?
(2)每次挑选重量最小的宝物装入,能否得到最优解?
(3)每次选取单位重量价值最大的宝物,能否使价值最高?
思考一下,如果选价值最大的宝物,但重量非常大,也是不行的,因为运载能力是有限
的,所以第 1 种策略舍弃;如果选重量最小的物品装入,那么其价值不一定高,所以不能在
总重限制的情况下保证价值最大,第 2 种策略舍弃;而第 3 种是每次选取单位重量价值最大
的宝物,也就是说每次选择性价比(价值/重量)最高的宝物,如果可以达到运载重量 m,

那么一定能得到价值最大。
因此采用第 3 种贪心策略,每次从剩下的宝物中选择性价比最高的宝物。

算法设计:
(1)数据结构及初始化。将 n 种宝物的重量和价值存储在结构体 three(包含重量、价
值、性价比 3 个成员)中,同时求出每种宝物的性价比也存储在对应的结构体 three 中,将
其按照性价比从高到低排序。采用 sum 来存储毛驴能够运走的最大价值,初始化为 0。
(2)根据贪心策略,按照性价比从大到小选取宝物,直到达到毛驴的运载能力。每次选
择性价比高的物品,判断是否小于 m(毛驴运载能力),如果小于 m,则放入,sum(已放入
物品的价值)加上当前宝物的价值,m 减去放入宝物的重量;如果不小于 m,则取该宝物的
一部分 m * p[i],m=0,程序结束。m 减少到 0,则 sum 得到最大值。

完美图解
假设现在有一批宝物,价值和重量如表 2-3 所示,毛驴运载能力 m=30,那么怎么装入
最大价值的物品?
宝物清单:

1
2
3
宝物 i  1  2  3  4  5  6  7  8  9  10
重量 w[i] 4 2 9 5 5 8 5 4 5 5
价值 v[i] 3 8 18 6 8 20 5 6 7 15

(1)因为贪心策略是每次选择性价比(价值/重量)高的宝物,按照性价比降序排序:
排序后宝物清单:

1
2
3
4
宝物 i  2  10  6  3  5  8  9  4  7  1
重量 w[i] 2 5 8 9 5 4 5 5 5 4
价值 v[i] 8 15 20 18 8 6 7 6 5 3
性价比 p[i] 4 3 2.5 2 1.6 1.5 1.4 1.2 1 0.75

(2)按照贪心策略,每次选择性价比高的宝物放入:
第 1 次选择宝物 2,剩余容量 30−2=28,目前装入最大价值为 8。
第 2 次选择宝物 10,剩余容量 28−5=23,目前装入最大价值为 8+15=23。
第 3 次选择宝物 6,剩余容量 23−8=15,目前装入最大价值为 23+20=43。
第 4 次选择宝物 3,剩余容量 15−9=6,目前装入最大价值为 43+18=61。

第 5 次选择宝物 5,剩余容量 6−5=1,目前装入最大价值为 61+8=69。
第 6 次选择宝物 8,发现上次处理完时剩余容量为 1,而 8 号宝物重量为 4,无法全部
放入,那么可以采用部分装入的形式,装入 1 个重量单位,因为 8 号宝物的单位重量价值为
1.5,因此放入价值 1×1.5=1.5,你也可以认为装入了 8 号宝物的 1/4,目前装入最大价值为
69+1.5=70.5,剩余容量为 0。
(3)构造最优解
把这些放入的宝物序号组合在一起,就得到了最优解(2,10,6,3,5,8),其中最后
一个宝物为部分装入(装了 8 号财宝的 1/4),能够装入宝物的最大价值为 70.5。

伪代码详解

(1)数据结构定义
根据算法设计中的数据结构,我们首先定义一个结构体 three:
struct three{
double w; //每种宝物的重量
double v; //每种宝物的价值
double p; //每种宝物的性价比(价值/重量)

(2)性价比排序
我们可以利用 C++中的排序函数 sort(见附录 B),对宝物的性价比从大到小(非递增)
排序。要使用此函数需引入头文件:
#include
语法描述为:
sort(begin, end)// 参数 begin 和 end 表示一个范围,分别为待排序数组的首地址和尾地址
在本例中我们采用结构体形式存储,按结构体中的一个字段,即按性价比排序。如果不
使用自定义比较函数,那么 sort 函数排序时不知道按哪一项的值排序,因此采用自定义比较
函数的办法实现宝物性价比的降序排序:
bool cmp(three a,three b)//比较函数按照宝物性价比降序排列
{
return a.p > b.p; //指明按照宝物性价比降序排列
}
sort(s, s+n, cmp); //前两个参数分别为待排序数组的首地址和尾地址
//最后一个参数 compare 表示比较的类型
(3)贪心算法求解
在性价比排序的基础上,进行贪心算法运算。如果剩余容量比当前宝物的重量大,则可以放入,剩余容量减去当前宝物的重量,已放入物品的价值加上当前宝物的价值。如果剩余
容量比当前宝物的重量小,表示不可以全部放入,可以切割下来一部分(正好是剩余容量),
然后令剩余容量乘以当前物品的单位重量价值,已放入物品的价值加上该价值,即为能放入
宝物的最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i = 0;i < n;i++)//按照排好的顺序,执行贪心策略
{
if( m > s[i].w )//如果宝物的重量小于毛驴剩下的运载能力,即剩余容量
{
m -= s[i].w;
sum += s[i].v;
}
else //如果宝物的重量大于毛驴剩下的承载能力
{
sum += m 乘以 s[i].p; //进行宝物切割,切割一部分(m 重量),正好达到驴子承重
break;
}
}

实现代码:

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
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
using namespace std;
const int M=1000005;
struct three{
double w;//每个宝物的重量
double v;//每个宝物的价值
double p;//性价比
}s[M];
bool cmp(three a,three b)
{
return a.p>b.p;//根据宝物的单位价值从大到小排序
}
int main()
{
int n;//n 表示有 n 个宝物
double m ;//m 表示毛驴的承载能力
cout<<"请输入宝物数量 n 及毛驴的承载能力 m :"<<endl;
cin>>n>>m;
cout<<"请输入每个宝物的重量和价值,用空格分开: "<<endl;
for(int i=0;i<n;i++)
{
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;//每个宝物单位价值
}
sort(s,s+n,cmp);
double sum=0.0;// sum 表示贪心记录运走宝物的价值之和
for(int i=0;i<n;i++)//按照排好的顺序贪心
{
if( m>s[i].w )//如果宝物的重量小于毛驴剩下的承载能力
{
m-=s[i].w;
sum+=s[i].v;
}
else//如果宝物的重量大于毛驴剩下的承载能力
{
sum+=m * s[i].p;//部分装入
break;
}
}
cout<<"装入宝物的最大价值 Maximum value="<<sum<<endl;
return 0;
}

注意

如果物品不能被分割,就不能采用贪心算法。

leetcode12. 整数转罗马数字

生活中的经验:

在以前还使用现金购物的时候,如果我们不想让对方找钱,付款的时候我们会尽量选择面值大的纸币给对方,这样才会使得我们给对方的纸币张数最少,对方点钱的时候也最方便。

本题“整数转罗马数字”也有类似的思想:在表示一个较大整数的时候,“罗马数字”的设计者不会让你都用 11 加起来,我们总是希望写出来的“罗马数字”的个数越少越好,以方便表示,并且这种表示方式还应该是唯一的。

“罗马数字”与阿拉伯数字的对应关系表中,并且按照从大到小的顺序排列

罗马数字 阿拉伯数字
M 1000
CM 900
D 500
CD 400
C 100
XC 90
L 50
XL 40
X 10
IX 9
V 5
IV 4
I 1

于是,“将整数转换为罗马数字”的过程,就是用上面这张表中右边的数字作为“加法因子”去分解一个整数,目的是“分解的整数个数”尽可能少,因此,对于这道问题,类似于用最少的纸币凑成一个整数,贪心算法的规则如下:

每一步都使用当前较大的罗马数字作为加法因子,最后得到罗马数字表示就是长度最少的。

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
public class Solution {

public String intToRoman(int num) {
// 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系,放在两个数组中
// 并且按照阿拉伯数字的大小降序排列,这是贪心选择思想
int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

StringBuilder stringBuilder = new StringBuilder();
int index = 0;
while (index < 13) {
// 特别注意:这里是等号
while (num >= nums[index]) {
// 注意:这里是等于号,表示尽量使用大的"面值"
stringBuilder.append(romans[index]);
num -= nums[index];
}
index++;
}
return stringBuilder.toString();
}
}

作者:liweiwei1419
链接:https://leetcode-cn.com/problems/integer-to-roman/solution/tan-xin-suan-fa-by-liweiwei1419/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

参考文章:
参考链接1
参考链接2

作者

byte4sec

发布于

2019-12-22

更新于

2020-12-31

许可协议

评论