经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » 编程经验 » 查看文章
贪心法求解问题
来源：cnblogs　　作者：jzhszy　　时间：2023/10/25 13:02:15　　对本文有异议

一、背包问题

1.1 问题描述

设有编号为1、2、......、n的n个物品，它们的重量分别为w1、w2、......、wn，价值分别为v1、v2、......、vn，其中wi和vi均为正数，有一个背包可以懈怠的最大重量不超过W。求解目标是在不超过背包附中的前提下使背包装入的总价值最大（即效益最大化）。与0/1背包问题的区别是，这里的每个物品可以取一部分装入背包。

1.2 求解思路

采用贪心法求解。用结构体存储物品的价值、重量和价重比，在输入价值重量后，首先求每个物品的价重比p=v/w，将所有物品按照价重比进行排序，从价重比最大的物品开始遍历，若当前物品的重量小于背包剩余容量wieght，将这个物品全部放入背包中，直到其中一个物品的重量w大于背包剩余容量或者物品放完，若其中一个物品的重量w大于背包剩余容量，就将其一部分装入背包，剩余若还有物品没装，便置为0。

1.3 详细代码

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAXV 51
  6. struct NodeType{
  7. 	double v;//价值
  8. 	double w;//重量
  9. 	double p;//价重比 
  10. }; 
  12. int n;		 //物品件数 
  13. double W;//背包限重 
  14. NodeType a[MAXV]={{0}};//所有物品
  16. double sumv=0;		 //当前背包中物品价值
  17. double x[MAXV]={0};//标记每件物品装了多少进背包 
  19. void KNap(){
  20. 	double weight=W;//背包剩余重量
  21. 	int i;
  22. 	for(i=0;i<n;i++){
  23. 		if(a[i].w<weight){//从价重比最大的开始，若能直接装入，就直接装入 
  24. 			x[i]=1;
  25. 			weight-=a[i].w;
  26. 			sumv+=a[i].v;
  27. 		}
  28. 		else if(a[i].w>weight){//直到其中一个不能完全装入，退出循环 
  29. 			break;
  30. 		}
  31. 	} 
  32. 	if(weight>0){//还能继续装入 
  33. 		x[i]=weight/a[i].w;			//这件物品装入一部分 
  34. 		sumv+=x[i]*a[i].v;
  35. 	}
  36. }
  38. bool cmp(NodeType p1,NodeType p2){//排序 
  39. 	return p1.p>p2.p;
  40. }
  42. void Disp(){				//输出 
  43. 	cout<<"W\t"<<"V\t"<<"V/W"<<endl; 
  44. 	for(int i=0;i<n;i++){
  45. 		cout<<a[i].v<<"\t"<<a[i].w<<"\t"<<a[i].p<<endl;
  46. 	}
  47. }
  48. void Init(){
  49. 	cout<<"请输入物品件数："<<endl;
  50. 	cin>>n;
  51. 	cout<<"请输入背包限重："<<endl;
  52. 	cin>>W;
  53. 	cout<<"请输入物品重量和价值："<<endl;
  54. 	double v,w;
  55. 	for(int i=0;i<n;i++){
  56. 		cout<<"第"<<i+1<<"件物品：";
  57. 		cin>>w>>v;
  58. 		a[i].v=v;
  59. 		a[i].w=w;
  60. 		a[i].p=v/w;
  61. 	}
  62. 	cout<<"排序前："<<endl;
  63. 	Disp(); 
  64. 	sort(a,a+n,cmp);		//排序 
  65. 	cout<<"排序后："<<endl;
  66. 	Disp();
  67. 	KNap();
  68. 	cout<<"求解结果："<<endl;
  69. 	cout<<"x：[ ";
  70. 	for(int i=0;i<n;i++){
  71. 		if(i==n-1) cout<<x[i];
  72. 		else cout<<x[i]<<" , ";
  73. 	}
  74. 	cout<<"]"<<endl;
  75. 	cout<<"总价值："<<sumv<<endl;
  76. }
  78. int main(){
  79. 	Init();
  80. 	return 0;
  81. }

1.4 复杂度分析

排序算法时间复杂度O(nlogn)，while循环时间复杂度为O(n)，所以本算法的时间复杂度为O(nlogn)。

二、最优装载问题

2.1 问题描述

有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1<=i<=n）的重量为wi。不考虑集装箱的体积限制，现要尽可能多的集装箱装上轮船，使他们的重量之和不超过W。

2.2 求解思路

题说要尽可能多的集装箱装上轮船，这里采用贪心法求解，选出尽可能多的集装箱个数。因此，当重量限制为W时，wi越小可装载的集装箱个数越多，所以采用优先选取重量轻的集装箱装船。对于已有的集装箱重量数组w[n]，通过sort排序对重量按照从小到大的顺序进行排序，并设置一个标记数组x[n]，标记集装箱是否被装入，0表示未被装入，1表示已被装入，船剩余载重量weight，船当前载重maxw。遍历数组w，当w[i]<weight时，将其装入，设x[i]=1，weight-=w[i]，maxw+=w[i]。直到集装箱被完全装入或剩余集装箱装不进时，退出循环，求解完毕。maxw即为最后轮船上的总重量。

2.3 详细代码

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAXV 51
  6. int w[]={0,5,2,4,3};//每个集装箱的重量
  7. int n=5,W=10;		// 5个集装箱，船载重为W
  8. int maxw=0;			//存放最优解重量
  9. int x[MAXV]={0};	//标记物品是否被存放 
  11. bool cmp(int a,int b){
  12. 	return a<b;
  13. }
  15. void solve(){
  16. 	int resw=W;
  17. 	sort(w+1,w+n+1,cmp);//对重量进行排序
  18. 	for(int i=1;i<=n&&w[i]<=resw;i++){
  19. 		maxw+=w[i];
  20. 		x[i]=1;
  21. 		resw-=w[i];
  22. 	}
  23. }
  25. int main(){
  26. 	solve();
  27. 	cout<<"最优方案为："<<endl; 
  28. 	for(int i=1;i<=n;i++){
  29. 		if(x[i]==1) cout<<w[i]<<" ";
  30. 	}
  31. 	cout<<endl;
  32. 	cout<<"最优解重量为："<<maxw<<endl;
  33. 	return 0;
  34. }

2.4 时间复杂度分析

快速排序时间复杂度为O(nlogn)，遍历重量时间复杂度为O(n)，故本算法时间复杂度为O(nlogn)。

三、田忌赛马问题

3.1 问题描述

两千多年前的战国时期，齐威王与大将田忌赛马。双方约定每人各出300匹马，并且在上、中、下三个等级中各选一匹进行比赛，由于齐威王每个等级的马都比田忌的马略强，比赛的结果可想而知。现在双方各n匹马，依次派出一匹马进行比赛，每一轮获胜的一方将从输的一方得到200银币，平局则不用出钱，田忌已知所有马的速度值并可以安排出场顺序，问他如何安排比赛获得的银币最多。输入描述：输入包含多个测试用例，每个测试用例的第一行正整数n（n≤1000）马的数量，后两行分别是n个整数，表示田忌和齐威王的马的速度值。输入n=0结束。输出描述：每个测试用例输出一行，表示田忌获得的最多银币数。

3.2 求解思路

采用贪心算法。令田忌马的速度数组为t[n]，左右两侧分别为leftt、rightt，齐威王马的速度数组为q[n]，左右两侧分别为leftq,rightq。田忌获得的银币即为monry。田忌赛马问题可以分为以下几种情况：
（1）田忌最快的马比齐威王最快的马快。此时最优解就是两者比赛，田忌赢。此时rightt--，rightq--，money+=200；
（2）田忌最快的马比齐威王最快的马慢。此时最优解是用田忌最慢的马与齐威王最快的马比赛，田忌输。此时leftt++，rightq--，money-=200；
（3）田忌最快的马和齐威王最快的马一样快。此时又分为以下三种情况：
??1、田忌最慢的马比齐威王最慢的马快。此时最优解就是两者比赛，田忌赢。此时leftt++，leftq++，money+=200；
??2、田忌最慢的马比齐威王最慢的马慢。此时最优解就是用田忌最慢的马与齐威王最快的马比赛，田忌输。此时leftt++，rightq--，money-=200；
??3、其他情况。平局。

3.3 详细代码

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAXV 1001
  6. int n;			//马总数
  7. int t[MAXV];	//田忌 
  8. int q[MAXV];	//齐威王
  9. int money=0;	//田忌获得的银币总数 
  11. void solve(){
  12. 	sort(t,t+n);//将马的速度按从小到大排序 
  13. 	sort(q,q+n);
  14. 	int leftt=0;
  15. 	int leftq=0;
  16. 	int rightt=n-1;
  17. 	int rightq=n-1;
  18. 	while(leftt<=rightt){
  19. 		if(t[rightt]>q[rightq]){//田忌最快的马齐威王最快的马快，田忌赢 
  20. 			money+=200;
  21. 			rightt--;
  22. 			rightq--;
  23. 		}
  24. 		else if(t[rightt]<q[rightq]){//田忌最快的马比齐威王最快的马慢 
  25. 			money-=200;
  26. 			leftt++;			//最优解为田忌用最慢的马与齐威王比，田忌输 
  27. 			rightq--;
  28. 		}
  29. 		else {					////田忌最快的马与齐威王最快的马速度相同 
  30. 			if(t[leftt]>q[leftq]){//田忌最慢的马比齐威王最慢的马快，田忌赢 
  31. 				money+=200;
  32. 				leftt++;
  33. 				leftq++;
  34. 			}
  35. 			else if(t[leftt]<q[leftq]){//田忌最慢的马比齐威王最慢的马慢 
  36. 				money-=200;
  37. 				leftt++;		//最优解为田忌最慢的马与齐威王最快的马比，田忌输 
  38. 				rightq--;
  39. 			}
  40. 		}
  41. 	}
  42. }
  44. int main(){
  45. 	while(true){
  46. 		cout<<"请输入马的总数：";
  47. 		cin>>n;
  48. 		if(n==0) return 0;
  49. 		cout<<"请输入田忌各匹马的速度："<<endl;
  50. 		for(int i=0;i<n;i++){
  51. 			cin>>t[i];
  52. 		}
  53. 		cout<<"请输入齐威王各匹马的速度："<<endl;
  54. 		for(int i=0;i<n;i++){
  55. 			cin>>q[i];
  56. 		}
  57. 		solve();
  58. 		cout<<"田忌能获得的银币最多为："<<money;
  59. 	}
  60. 	return 0;
  61. } `
  62. #### 3.4 时间复杂度分析
  63. &emsp;&emsp;算法主要花费在快速排序，因此时间复杂度为O(nlogn)。
  64. ## 四、多机调度问题
  65. #### 4.1 问题描述
  66. &emsp;&emsp;设有n个独立的作业{1,2,......,n}，由m台相同的及其{1,2,......,m}进行加工处理，作业i所需的处理时间为ti（1<=i<=n），每个作业均可在任何一台及其上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
  67. #### 4.2 问题求解
  68. &emsp;&emsp;采用贪心法求解。题说要求在尽可能短的时间内完成，因此分为两种情况，当n<=m时，机器比作业多，可以为每个作业分配一台机器。当n>m时，作业比机器多，此时考虑长作业优先（因为短作业优先时，最开始每个机器上都是短作业，最后分配长作业会发现非常耗时），使用结构体NodeType存储每个作业，包括no（作业编号）、t（时间）、mmo（分配的机器编号）。首先对结构体数组A[n]按照时间从大到小进行排序，先把每个机器上分配一个作业，使用小根堆qu（小根堆会自动排序）来存放结构体，分配下一轮作业时，按照上一轮作业完成时间越小越先出队即e=qu.top()，qu.pop()。出队后将机器分配给下一个作业，并加上时间A[i].t，在将其添加到小根堆中，直到作业分配完毕。
  69. #### 4.3 详细代码
  70. `#include<iostream>
  71. #include<queue>
  72. #include<vector>
  73. #include<algorithm>
  74. using namespace std;
  76. int n=7;	//n个作业
  77. int m=3;	//m个机器 
  78. struct NodeType{
  79. 	int no;//作业序号
  80. 	int t;//作业时长
  81. 	int mmo;//机器序号
  82. 	bool operator < (const NodeType& s) const{//按t从大到小排序 
  83. 		return t>s.t;
  84. 	} 
  85. };
  86. NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; 
  88. void solve(){
  89. 	NodeType e;
  90. 	if(n<=m){
  91. 		cout<<"为每一个作业分配一台机器"<<endl;
  92. 		return ;
  93. 	}
  94. 	sort(A,A+n);
  95. 	priority_queue<NodeType,vector<NodeType>,less<NodeType> > qu;//小根堆，小的元素在上面（自动排序） 
  96. 	for(int i=0;i<m;i++){
  97. 		A[i].mmo=i+1;
  98. 		cout<<"给机器"<<i+1<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段[0,"<<A[i].t<<"]"<<endl;
  99. 		qu.push(A[i]);
  100. 	}
  101. 	for(int i=m;i<n;i++){
  102. 		e=qu.top();
  103. 		qu.pop();
  104. 		cout<<"给机器"<<e.mmo<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段["<<e.t<<","<<e.t+A[i].t<<"]"<<endl;
  105. 		e.t+=A[i].t; 
  106. 		qu.push(e);
  107. 	}
  108. }
  110. int main(){
  111. 	cout<<"多机调度问题："<<endl;
  112. 	solve();
  113. 	return 0;
  114. }`
  115. #### 4.4 时间复杂度分析
  116. &emsp;&emsp;算法快速排序时间复杂度O(nlogn)，两次for循环时间复杂度共O(n)，因此本算法时间复杂度为O(nlogn)。
  117. #### 4.5 小根堆（之前对小根堆了解不多下面记录一下堆）
  118. 1、大根堆：是完全二叉树，其中根结点大于子节点；小根堆：是完全二叉树，其中根结点小于子节点。
  119. 2、c++中，小根堆和大根堆可以使用优先队列实现（priority_queue），优先级高的先出队，自动排序。
  120. `#include<queue>
  121. priority_queue<int> qu;//默认是大根堆
  122. priority_queue<int,vector<int>,greater<int> > qu;//小根堆
  123. priority_queue<int,vector<int>,less<int> > qu;//大根堆
  124. `
  125. 在使用结构体时
  126. `#include<queue>
  127. struct Node{
  128.   int x,y;
  129.   bool operator < (const Node& a)const{//小的先进堆
  130.     return x<a.x;
  131.   }
  132. };
  133. priority_queue<Node,vector<Node>,less<Node> > qu;//按照重载后的小于规则，从大到小排序，大的优先级高
  134. `

原文链接：https://www.cnblogs.com/QwertyWang/p/GreedyAlgorithm_1.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

编程经验热门文章

  • Prometheus监控之SNMP Exporter介绍和数据展现
  • Intel 82599网卡异常挂死原因
  • 腾讯防水墙的分析识别与破解
  • 桌面应用自动化WinAppDriver入门
  • 文档在线预览（三）使用js前端实现word、excel、pdf、ppt 在线预览
  • 「教程」如何下载AcFun网站上的视频、A站视频下载工具
  • 基于Hi3559AV100的SVP(NNIE)开发整体流程
  • GBDT(梯度提升树)scikit-klearn中的参数说明及简汇
  • antd之RangePicker设置默认值方式
  • 决胜经典算法之插入排序

    • 编程经验推荐文章

  • wifi基础(一)：无线电波与WIFI信号干扰、衰减
  • 甲方扔给两个存在包名与类名均相同的Jar包，要在工程中同时使用怎么办？
  • 《花100块做个摸鱼小网站! 》第三篇—热搜表结构设计和热搜数据存储
  • Fluent Editor：一个基于 Quill 2.0 的富文本编辑器，功能强大、开箱即用！
  • 方法的三种调用形式
  • 《花100块做个摸鱼小网站! 》第二篇—后端应用搭建和完成第一个爬虫
  • 《熬夜整理》保姆级系列教程-玩转Wireshark抓包神器教程(4)-再识Wireshark - 北京-宏哥
  • 《软件性能测试分析与调优实践之路》(第2版) 读书笔记（二）总体介绍（下）-真正从性能分析与调优来看性能测试
  • 架构知识点（三）
  • 《花100块做个摸鱼小网站! 》第一篇—买云服务器和初始化环境

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号