贪心算法问题1(西红柿首富的烦恼):
王多鱼获得了一笔的奖金X,要求购买最少的商品把钱花光,即没有零钱剩下,否则奖金会被没收。
输入:
一个整数k:商品的种类(每个种类商品个数不限);
第i类商品的价值a[i];
一个整数m:奖金总额;
输出:
最少商品数量
举例:
输入:
7
1 2 5 10 20 50 100
288
输出:
8
代码:
c++代码实现(贪心算法):
/**王多鱼问题*/
#include <iostream>
using namespace std;
int main()
{
int k,n,m,cnt=0,a[1000];
cout << "商品的种类" << endl;
cin>>k;
cout << "从小到大输入商品的价值" << endl;
for(int i=1;i<=k;i++)
cin>>a[i];
cout << "输入奖金总额" << endl;
cin>>m;
for(int i=k;i>=1;i--){
if(m>=a[i]){
n = m/a[i];
m = m - n*a[i];
cnt +=n;
cout<<a[i]<<"元的商品:"<<n<<"个"<<endl;
if(m==0)
break;
}
}
cout<<"最少的商品数量:"<<cnt<<endl;
return 0;
}
测试结果:
贪心算法问题2(西红柿首富的烦恼升级):
王多鱼获得了一笔的奖金X,要求购买最少的商品把钱花光,即没有零钱剩下,否则奖金会被没收。
输入:
一个整数k:商品的种类(每个种类商品个数有限);
第i类商品的价值a[i];
第i类商品的数量b[i];
一个整数m:奖金总额;
输出:
最少商品数量
举例:
输入:
7
1 2 5 10 20 50 100
5 5 5 5 5 5 1
288
输出:
9
代码:
c++代码实现(贪心算法):
/**王多鱼问题*/
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
int k,n,m,p,cnt=0,a[1000],b[1000];
cout << "商品的种类" << endl;
cin>>k;
cout << "从小到大输入商品的价值" << endl;
for(int i=1;i<=k;i++)
cin>>a[i];
cout << "依次输入每类商品的数量" << endl;
for(int i=1;i<=k;i++)
cin>>b[i];
cout << "输入奖金总额" << endl;
cin>>m;
for(int i=k;i>=1;i--){
if(m>=a[i]){
n = m/a[i];
p = min(n,b[i]);
m = m - p*a[i];
cnt +=p;
cout<<a[i]<<"元的商品:"<<p<<"个"<<endl;
if(m==0)
break;
}
}
cout<<"最少的商品数量:"<<cnt<<endl;
return 0;
}
测试结果:
贪心算法问题3(最多课程问题):
start_time |
8 |
9 |
10 |
12 |
13 |
end_time |
11 |
10 |
15 |
14 |
15 |
一天有n节课,输入起止时间,每节课时间不能冲突,求这一天最多能上多少节课?
输入:
课程起止时间(按时间先后顺序输入),以‘q’结束;
输出:
最多能上多少节课
举例:
输入:
8,11
9,10
10,15
12,14
13,15
q
输出:
2
#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
using namespace std;
typedef struct Suject_time{
int begin_time; //课程开始时间
int end_time; //课程结束时间
}suject_time;
int main()
{
vector<suject_time>Subject;
string s,p,s1,s2;
int cnt=1;
suject_time tmp;
cout << "输入起止时间,输入'q'字符结束" << endl;
cin >>s;
//p = s.substr(s.find(","));
//s1 = s.substr(s.find_first_not_of(","),s.size()-p.size());
//s2 = s.substr(s.find_first_of(",")+1,p.size()-1);
//cout <<s1<< endl;
//cout <<s2<< endl;
while(s[0]!='q'){
p = s.substr(s.find(","));
s1 = s.substr(s.find_first_not_of(","),s.size()-p.size());
s2 = s.substr(s.find_first_of(",")+1,p.size()-1);
tmp.begin_time = stoi(s1);
tmp.end_time = stoi(s2);
Subject.push_back(tmp);
cin>>s; //循环输入起止时间
}
for(int i=0;i<Subject.size();){
for(int j=i+1;i<Subject.size();j++){
if(Subject[j].begin_time>=Subject[i].end_time){
i =j;
cnt++; //计数
break;
}
else
i++;
}
}
Subject.begin.
cout<<"最大能上课程数:"<<cnt<<endl;
return 0;
}
测试:
贪心算法问题4(最多课程问题升级):
start_time |
13 |
10 |
13 |
15 |
11 |
end_time |
17 |
16 |
15 |
17 |
13 |
一天有n节课,输入起止时间,每节课时间不能冲突,求这一天最多能上多少节课?
输入:
课程数量n
每个课程的起止时间(乱序)
输出:
最多能上多少节课
举例:
输入:
13 17
10 16
13 15
15 17
11 13
输出:
3
代码:
#include <iostream>
#include <vector>
#include <map> //map(key-vaule) 每个key按顺序排列,不可改变和重复,value可以改变
#include <list> //set只有一个key,每个key按顺序排列,不可重复可改变
#include <cstring>
#include <string.h>
using namespace std;
typedef struct Suject_time{
int begin_time; //课程开始时间
int end_time; //课程结束时间
int sustained_time; //课程持续时间
}suject_time;
list<suject_time>s;
list<suject_time>::iterator iter,iter1,iter2,iter3,iter4; //指针迭代器
//map<int,int>::iterator iter; //map迭代器
//map<int,int>s; //定义map
int n,cnt=1,maxcnt=1;
bool compare_begin_time(const suject_time tmp1, const suject_time tmp2){
return (tmp1.begin_time < tmp2.begin_time);
}
//根据sustained_time初步帅选最佳的课程
void saixuan(){
for(iter = s.begin(); iter != s.end(); iter++){
for(iter1 = s.begin(); iter1 != s.end();iter1++){
if(iter->begin_time==iter1->begin_time){
if(iter->sustained_time>iter1->sustained_time){
s.erase(iter);
iter = s.begin(); //不像数组,erase后长度变小,指针需要重新指向begin
break;
}
if(iter->sustained_time<iter1->sustained_time){
s.erase(iter1);
iter = s.begin(); //不像数组,erase后长度变小,指针需要重新指向begin
break;
}
}
}
}
}
//贪心
void tanxin(){
for(iter2 = s.begin(); iter2 != s.end();iter2++){
for(iter3 = iter2; iter3 != s.end();){
for(iter4 = ++iter3; iter4 != s.end();iter4++){
iter3--;
if(iter4->begin_time>=iter3->end_time){
//cout<<iter4->begin_time<<">"<<iter3->end_time<<endl;
iter3 =iter4;
cnt++; //计数
break;
}
else
iter3++;
}
}
if(maxcnt<cnt)
maxcnt = cnt;
cnt = 1;
}
}
int main()
{
suject_time tmp;
string s1,s2;
cout<<"输入课程数量:"<<endl;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s1;
cin>>s2;
tmp.begin_time=stoi(s1);
tmp.end_time=stoi(s2);
tmp.sustained_time=tmp.end_time-tmp.begin_time;
//s[tmp.begin_time] = tmp.end_time; //map映射
s.push_back(tmp);
}
saixuan();
//list的插入和删除
tmp.begin_time=10;
tmp.end_time=100;
tmp.sustained_time=90;
s.insert(s.begin(),tmp);
s.erase(s.begin());
s.sort(compare_begin_time);
//**输出
cout<<"筛选之后:"<<endl;
for(iter2 = s.begin(); iter2 != s.end(); iter2++) //map、list、set都是指针操作,vector可以用[]操作符
//cout<<iter->first<<' '<<iter->second<<endl;
cout<<iter2->begin_time<<" "<<iter2->end_time<<endl;
tanxin();
cout<<"最大能上课程数:"<<maxcnt<<endl;
//}
return 0;
}
测试:
贪心算法问题5(排队打水最少等待时间问题):
有n个人排队到r个水龙头去打水,他们装满水桶的时间t1、t2………..tn为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少?
输入:
排队人数n,水龙头个数r
每个人的打水时间a[i]
输出:
至少花费时间
举例:
输入:
5 2
1 2 3 4 6
输出:
22
代码:
#include<iostream>
#include<queue>
#include<stdlib.h>
#include <algorithm>
using namespace std;
/**
class T
{
public:
int x,y,z;
T(int a,int b,int c):x(a),y(b),z(c)
{
}
};*/
class T
{
public:
int x;
T(int a):x(a)
{
}
};
bool operator<(const T&t1,const T&t2)
{
return t1.x>t2.x; //从小到大出队
}
int a[500];
int main(){
int n,r,i,re;
priority_queue<T>q;
cout<<"分别输入排队人数和水龙头数:"<<endl;
while(cin>>n>>r){
re=0;
cout<<"输入每个人打水时间:"<<endl;
for(i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
for(i=0;i<r;i++){
q.push(T(a[i]));
re+=a[i];
}
for(i=r;i<n;i++){
T t=q.top();
int tmp = t.x+a[i];
re+=tmp;
q.pop();
q.push(tmp);
}
while(!q.empty()){
q.pop();
}
cout<<"最少排队时间:"<<re<<endl;
}
return 0;
}
测试: