贪心算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了贪心算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7924字,纯文字阅读大概需要12分钟。
内容图文
背包问题:
背包问题就是在背包载荷已经给定的情况下,每次把单位价值最高的物品放入背包中知道所有物品放完或者背包中物品的重量达到给定载荷。
一般是用结构体来做;
for(int i=0;i<n;i++){
v[i]=p[i]/w[i]; //p是每个物品的价值,w是每个物品的重量
}
//然后对物品的单位价值由高到低排序
W=0,P=0; //设定背包一开始的包内物品重量和价值
while(W<M){
if(M-W-w[i]>=0){ //如果这个物品可以完全放进背包里且不超载
W+=w[i];
P+=p[i];
}
else{ //如果这个物品没办法完全放进背包,则放入一部分进背包
P+=(M-W)*v[i]; //v为每个物品的单位价值,背包内还能容纳的物品重量*v就是后来放入的物品的价值
W=M; //背包最多只能重M
}
}
例题:
FatMouse’ Trade
FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.
The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.
Input
The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1’s. All integers are not greater than 1000.
Output
For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.
Sample Input
5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1
Sample Output
13.333
31.500
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
struct point{
double j;
double f;
double a;
}room[1005];
bool cmp(point ai,point bi){
return ai.a>bi.a;
}
int main(int argc,char const*argv[]){
int m,n;
while(scanf("%d%d",&m,&n)!=EOF){
if(m==-1&n==-1) break;
for(int i=0;i<n;i++){
scanf("%lf%lf",&room[i].j,&room[i].f);
room[i].a=(room[i].j/room[i].f);
}
double J=0,F=0;
sort(room,room+n,cmp);
for(int i=0;i<n;i++){
if(m-F-room[i].f>=0){
F+=room[i].f;
J+=room[i].j;
}
else{
J+=(m-F)*room[i].a;
break;
}
}
printf("%.3f\n",J);
}
return 0;
}
任务调度问题:
有n项任务,每个任务的开始时间为si,结束时间为ei,一项任务只能在一个机器上完成,每台机器一次只能完成一项任务,如果任务i和任务j满足si>=ej或sj>=ei,那么i和j就可以在一台机器上工作。任务调度问题就是以不冲突的方式以尽可能少的机器完成所有任务。
解决这类问题就是每次都安排开始时间比较小的任务先完成。
一般用STL里面的容器来做,因为这样可以存两个值,一个开始时间一个结束时间。
有n个任务,num台机器
num=0;
for(int i=0;i<n;i++){
输入任务
}
对n项任务按开始时间进行排序
for(int i=0;i<n;i++){
if(任务i和已经执行的任务不冲突)
在已经执行任务的机器上工作
else{
num++;
任务i在新机器上完成
}
}
例题:Schedule
There are N schedules, the i-th schedule has start time si and end time ei (1 <= i <= N). There are some machines. Each two overlapping schedules cannot be performed in the same machine. For each machine the working time is defined as the difference between timeend and timestart , where time_{end} is time to turn off the machine and timestart is time to turn on the machine. We assume that the machine cannot be turned off between the timestart and the timeend.
Print the minimum number K of the machines for performing all schedules, and when only uses K machines, print the minimum sum of all working times.
Input
The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers si and ei (0<=si<ei<=1e9).
Output
For each test case, print the minimum possible number of machines and the minimum sum of all working times.
Sample Input
1
3
1 3
4 6
2 5
Sample Output
2 8
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<sstream>
#include<iomanip>
#include<set>
#define ll long long
using namespace std;
multiset<int>s;
multiset<int>::iterator it;
pair<int,int>a[100005];
int main(int argc,char const*argv[]){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n); //输入n个任务
s.clear(); //清空s容器
for(int i=0;i<n;i++){ //输入每个任务
scanf("%d%d",&a[i].first,&a[i].second); //first是开始时间,second是结束时间
}
sort(a,a+n); //默认以first的大小进行排序
int num=0; //用于统计机器的台数
long long ans=0; //用于统计时间
for(int i=0;i<n;i++){ //进入循环
if(s.empty()||(*s.begin())>a[i].first){ //s是空着的时候或者a[i]的开始时间小于前面的数的结束时间
num++; //再开一台机器
s.insert(a[i].second); //将a[i]的结束时间插入
ans-=a[i].first; //记录时间
}
else{
it=s.upper_bound(a[i].first); //在s容器中找一个比a[i].first大的数,让it指向这个数
it--; //指针往前移一位
s.erase(it); //删去it
s.insert(a[i].second); //这时将a[i]的结束时间插入
}
}
for(it=s.begin();it!=s.end();it++){ //迭代器从第一个开始
ans+=(*it);
}
printf("%d %lld\n",num,ans);
}
return 0;
}
区间调度问题:
区间调度和任务调度差不多。也是给出每个任务的开始时间和结束时间,但是只有一台机器,一台机器一次只能完成一个任务。求解这台机器最多可以完成多少任务。
一般的解法是每次都先完成结束时间最少的任务,就是在排序的时候先把任务按结束时间升序排列。
下面的例题:Gene Assembly
Statement of the Problem
With the large amount of genomic DNA sequence data being made available, it is becoming more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more complicated, because of the presence of junk DNA that interrupts the coding region of genes in the genomic sequence. That is, a gene is composed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary.
Most gene finding algorithms have two steps: in the first they search for possible exons; in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon i appears before exon j if the end of i precedes the beginning of j.
The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that cound be assembled to generate a gene.
Input Format
Several input instances are given. Each instance begins with the number 0 < n < 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single 0.
Output Format
For each input instance your program should print in one line the chain with the largest possible number of exons, by enumerating the exons in the chain. If there is more than one chain with the same number of exons, your program can print anyone of them.
Sample Input
6
340 500
220 470
100 300
880 943
525 556
612 776
3
705 773
124 337
453 665
0
Sample Output
3 1 5 6 4
2 3 1
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<sstream>
#include<iomanip>
#include<set>
#define ll long long
using namespace std;
struct point{
int first,second;
int poi;
}a[1005];
int cmp(point ai,point bi){
return ai.second<bi.second;
}
int main(int argc,char const*argv[]){
int n;
int ans[1005];
while(scanf("%d",&n)!=EOF){
if(n==0) break;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].first,&a[i].second);
a[i].poi=i;
}
sort(a+1,a+1+n,cmp);
int p=a[1].second;
int k=0;
ans[k++]=a[1].poi;
for(int i=2;i<=n;i++){
if(a[i].first>p){
p=a[i].second;
ans[k++]=a[i].poi;
}
}
for(int i=0;i<k;i++){
printf("%d",ans[i]);
if(i!=k-1) printf(" ");
}
printf("\n");
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的贪心算法全部内容,希望文章能够帮你解决贪心算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。