贪心法求解问题
一、背包问题
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 详细代码
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51
struct NodeType{
double v;//价值
double w;//重量
double p;//价重比
};
int n; //物品件数
double W;//背包限重
NodeType a[MAXV]={{0}};//所有物品
double sumv=0; //当前背包中物品价值
double x[MAXV]={0};//标记每件物品装了多少进背包
void KNap(){
double weight=W;//背包剩余重量
int i;
for(i=0;i<n;i++){
if(a[i].w<weight){//从价重比最大的开始，若能直接装入，就直接装入
x[i]=1;
weight-=a[i].w;
sumv+=a[i].v;
}
else if(a[i].w>weight){//直到其中一个不能完全装入，退出循环
break;
}
}
if(weight>0){//还能继续装入
x[i]=weight/a[i].w; //这件物品装入一部分
sumv+=x[i]*a[i].v;
}
}
bool cmp(NodeType p1,NodeType p2){//排序
return p1.p>p2.p;
}
void Disp(){ //输出
cout<<"W\t"<<"V\t"<<"V/W"<<endl;
for(int i=0;i<n;i++){
cout<<a[i].v<<"\t"<<a[i].w<<"\t"<<a[i].p<<endl;
}
}
void Init(){
cout<<"请输入物品件数："<<endl;
cin>>n;
cout<<"请输入背包限重："<<endl;
cin>>W;
cout<<"请输入物品重量和价值："<<endl;
double v,w;
for(int i=0;i<n;i++){
cout<<"第"<<i+1<<"件物品：";
cin>>w>>v;
a[i].v=v;
a[i].w=w;
a[i].p=v/w;
}
cout<<"排序前："<<endl;
Disp();
sort(a,a+n,cmp); //排序
cout<<"排序后："<<endl;
Disp();
KNap();
cout<<"求解结果："<<endl;
cout<<"x：[ ";
for(int i=0;i<n;i++){
if(i==n-1) cout<<x[i];
else cout<<x[i]<<" , ";
}
cout<<"]"<<endl;
cout<<"总价值："<<sumv<<endl;
}
int main(){
Init();
return 0;
}
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 详细代码
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 51
int w[]={0,5,2,4,3};//每个集装箱的重量
int n=5,W=10; // 5个集装箱，船载重为W
int maxw=0; //存放最优解重量
int x[MAXV]={0}; //标记物品是否被存放
bool cmp(int a,int b){
return a<b;
}
void solve(){
int resw=W;
sort(w+1,w+n+1,cmp);//对重量进行排序
for(int i=1;i<=n&&w[i]<=resw;i++){
maxw+=w[i];
x[i]=1;
resw-=w[i];
}
}
int main(){
solve();
cout<<"最优方案为："<<endl;
for(int i=1;i<=n;i++){
if(x[i]==1) cout<<w[i]<<" ";
}
cout<<endl;
cout<<"最优解重量为："<<maxw<<endl;
return 0;
}
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 详细代码
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXV 1001
int n; //马总数
int t[MAXV]; //田忌
int q[MAXV]; //齐威王
int money=0; //田忌获得的银币总数
void solve(){
sort(t,t+n);//将马的速度按从小到大排序
sort(q,q+n);
int leftt=0;
int leftq=0;
int rightt=n-1;
int rightq=n-1;
while(leftt<=rightt){
if(t[rightt]>q[rightq]){//田忌最快的马齐威王最快的马快，田忌赢
money+=200;
rightt--;
rightq--;
}
else if(t[rightt]<q[rightq]){//田忌最快的马比齐威王最快的马慢
money-=200;
leftt++; //最优解为田忌用最慢的马与齐威王比，田忌输
rightq--;
}
else { ////田忌最快的马与齐威王最快的马速度相同
if(t[leftt]>q[leftq]){//田忌最慢的马比齐威王最慢的马快，田忌赢
money+=200;
leftt++;
leftq++;
}
else if(t[leftt]<q[leftq]){//田忌最慢的马比齐威王最慢的马慢
money-=200;
leftt++; //最优解为田忌最慢的马与齐威王最快的马比，田忌输
rightq--;
}
}
}
}
int main(){
while(true){
cout<<"请输入马的总数：";
cin>>n;
if(n==0) return 0;
cout<<"请输入田忌各匹马的速度："<<endl;
for(int i=0;i<n;i++){
cin>>t[i];
}
cout<<"请输入齐威王各匹马的速度："<<endl;
for(int i=0;i<n;i++){
cin>>q[i];
}
solve();
cout<<"田忌能获得的银币最多为："<<money;
}
return 0;
}
3.4 时间复杂度分析
算法主要花费在快速排序，因此时间复杂度为O(nlogn)。
四、多机调度问题
4.1 问题描述
设有n个独立的作业{1,2,......,n}，由m台相同的及其{1,2,......,m}进行加工处理，作业i所需的处理时间为ti（1<=i<=n），每个作业均可在任何一台及其上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
4.2 问题求解
采用贪心法求解。题说要求在尽可能短的时间内完成，因此分为两种情况，当n<=m时，机器比作业多，可以为每个作业分配一台机器。当n>m时，作业比机器多，此时考虑长作业优先（因为短作业优先时，最开始每个机器上都是短作业，最后分配长作业会发现非常耗时），使用结构体NodeType存储每个作业，包括no（作业编号）、t（时间）、mmo（分配的机器编号）。首先对结构体数组A[n]按照时间从大到小进行排序，先把每个机器上分配一个作业，使用小根堆qu（小根堆会自动排序）来存放结构体，分配下一轮作业时，按照上一轮作业完成时间越小越先出队即e=qu.top()，qu.pop()。出队后将机器分配给下一个作业，并加上时间A[i].t，在将其添加到小根堆中，直到作业分配完毕。
4.3 详细代码
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n=7; //n个作业
int m=3; //m个机器
struct NodeType{
int no;//作业序号
int t;//作业时长
int mmo;//机器序号
bool operator < (const NodeType& s) const{//按t从大到小排序
return t>s.t;
}
};
NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}};
void solve(){
NodeType e;
if(n<=m){
cout<<"为每一个作业分配一台机器"<<endl;
return ;
}
sort(A,A+n);
priority_queue<NodeType,vector<NodeType>,less<NodeType> > qu;//小根堆，小的元素在上面（自动排序）
for(int i=0;i<m;i++){
A[i].mmo=i+1;
cout<<"给机器"<<i+1<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段[0,"<<A[i].t<<"]"<<endl;
qu.push(A[i]);
}
for(int i=m;i<n;i++){
e=qu.top();
qu.pop();
cout<<"给机器"<<e.mmo<<"分配作业"<<A[i].no<<"，执行时间为"<<A[i].t<<"，占用时间段["<<e.t<<","<<e.t+A[i].t<<"]"<<endl;
e.t+=A[i].t;
qu.push(e);
}
}
int main(){
cout<<"多机调度问题："<<endl;
solve();
return 0;
}
4.4 时间复杂度分析
算法快速排序时间复杂度O(nlogn)，两次for循环时间复杂度共O(n)，因此本算法时间复杂度为O(nlogn)。
4.5 小根堆（之前对小根堆了解不多下面记录一下堆）
1、大根堆：是完全二叉树，其中根结点大于子节点；小根堆：是完全二叉树，其中根结点小于子节点。
2、c++中，小根堆和大根堆可以使用优先队列实现（priority_queue），优先级高的先出队，自动排序。
#include<queue>
priority_queue<int> qu;//默认是大根堆
priority_queue<int,vector<int>,greater<int> > qu;//小根堆
priority_queue<int,vector<int>,less<int> > qu;//大根堆
在使用结构体时
#include<queue>
struct Node{
int x,y;
bool operator < (const Node& a)const{//小的先进堆
return x<a.x;
}
};
priority_queue<Node,vector<Node>,less<Node> > qu;//按照重载后的小于规则，从大到小排序，大的优先级高