贪心法求解问题

一、背包问题

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
#include
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;iweight){//直到其中一个不能完全装入，退出循环 
			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>n;
	cout>W;
	cout>w>>v;
		a[i].v=v;
		a[i].w=w;
		a[i].p=v/w;
	}
	cout

1.4 复杂度分析

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

二、最优装载问题

2.1 问题描述

  有n个集装箱要装上一艘载重量为W的轮船，其中集装箱i（1

2.2 求解思路

  题说要尽可能多的集装箱装上轮船，这里采用贪心法求解，选出尽可能多的集装箱个数。因此，当重量限制为W时，wi越小可装载的集装箱个数越多，所以采用优先选取重量轻的集装箱装船。对于已有的集装箱重量数组w[n]，通过sort排序对重量按照从小到大的顺序进行排序，并设置一个标记数组x[n]，标记集装箱是否被装入，0表示服务器托管网未被装入，1表示已被装入，船剩余载重量weight，船当前载重maxw。遍历数组w，当w[i]

2.3 详细代码

#include
#include
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

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
#include
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(lefttq[rightq]){//田忌最快的马齐威王最快的马快，田忌赢 
			money+=200;
			rightt--;
			rightq--;
		}
		else if(t[rightt]q[leftq]){//田忌最慢的马比齐威王最慢的马快，田忌赢 
				money+=200;
				leftt++;
				leftq++;
			}
			else if(t[leftt]>n;
		if(n==0) return 0;
		cout>t[i];
		}
		cout>q[i];
		}
		solve();
		cout

3.4 时间复杂度分析

  算法主要花费在快速排序，因此时间复杂度为O(nlogn)。

四、多机调度问题

4.1 问题描述

  设有n个独立的作业{1,2,……,n}，由m台相同的及其{1,2,……,m}进行加工处理，作业i所需的处理时间为ti（1

4.2 问题求解

  采用贪心法求解。题说要求在尽可能短的时间内完成，因此分为两种情况，当nm时，作业比机器多，此时考虑长作业优先（因为短作业优先时，最开始每个机器上都是短作业，最后分配长作业会发现非常耗时），使用结构体NodeType存储每个作业，包括no（作业编号）、t（时间）、mmo（分配的机器编号）。首先对结构体数组A[n]按照时间从大到小进行排序，先把每个机器上分配一个作业，使用小根堆qu（小根堆会自动排序）来存放结构体，分配下一轮作业时，按照上一轮作业完成时间越小越先出队即e=qu.top()，qu.pop()。出队后将机器分配给下一个作业，并加上时间A[i].t，在将其添加到小根堆中，直到作业分配完毕。

4.3 详细代码

#include
#include
#include
#include
using namespace std;

int n=7;	//n个作业
int m=3;	//m个机器 
struct NodeType{
	int no;//作业序号
	int t;//作业时长
	int mmo;//机器序号
	bool operator s.t;
	} 
};
NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; 

void solve(){
	NodeType e;
	if(n,less > qu;//小根堆，小的元素在上面（自动排序） 
	for(int i=0;i

4.4 时间复杂度分析

  算法快速排序时间复杂度O(nlogn)，两次for循环时间复杂度共O(n)，因此本算法时间复杂度为O(nlogn)。

4.5 小根堆（之前对小根堆了解不多下面记录一下堆）

1、大根堆：是完全二叉树，其中根结点大于子节点；小根堆：是完全二叉树，其中根结点小于子节点。
2、c++中，小根堆和大根堆可以使用优先队列实现（priority_queue），优先级高的先出队，自动排序。

#include
priority_queue qu;//默认是大根堆
priority_queue,greater > qu;//小根堆
priority_queue,less > qu;//大根堆

在使用结构体时

#include
struct Node{
  int x,y;
  bool operator ,less > qu;//按照重载后的小于规则，从大到小排序，大的优先级高

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Visual Studio 新建类从默认internal改为public
前言
修改步骤
总结

服务器托管网 前言 之前一直用的Resharp辅助编写C#代码，Resharp用起来的确方便不少，但是太消耗开发机内存了。重装电脑后，还是决定使用Visual Studio内置的功能。 默认情况下，Visual Studio 中生成一个类或接口是interna…