- 一.会场安排问题
#include<stdio.h>
/*
查找每个活动的结束时间，每一次选择时查找具有最早结束时间的相容的活动，先把n个活动按时间的结束时间非减序排列，这样，贪心选择是取当前活动集合中结束时间最早的活动就归结为取当前活动集合中排在最前面的活动*/
void sort(int s[],int f[],int n)//把各个活动的起始时间和结束时间按结束时间递增排序
{
??? int a,b;
??? int i,j;
??? for(i=0;i<n;i++)
??? {
??????? for(j=i+1;j<n;j++)
??????? {
??????????? if(f[i]>f[j])
??????????? {a=f[i];f[i]=f[j];f[j]=a;
??????????? b=s[i];s[i]=s[j];s[j]=b;}
??????? }
??? }
}
int activemanage(int s[],int f[],bool a[],int n)
{
??? a[0]=1;
??? int i;
??? int j=1,count=1;
??? for(i=1;i<n;i++)
??? {
??????? if(s[i]>=f[j])
??????? {
??????????? a[i]=1;
??????????? j=i;
??????????? count++;
??????? }
??????? else a[i]=0;
??? }
??? return count;
}
int main()
{
??? int i,n;
??? int p;
??? int s[100],f[100];
??? bool a[100];
??? printf("输入节目数：\n");
??? scanf("%d",&n);
??? printf("请依次输入节目的开始和结束时间\n");
??? for(i=0;i<n;i++)
??? {
??????? scanf("%d %d",&s[i],&f[i]);
??? }
??? sort(s,f,n);
??? p=activemanage(s,f,a,n);
??? printf("安排的节目个数为:%d\n",p);
??? printf("节目的选取情况为(0表示不选 1表示选取):\n");
??? for(i=0;i<n;i++)
??????? printf("%d ",a[i]);
??? printf("\n");
??? return 0;
}
二、最优装载问题
#include <iostream>
#include <algorithm>
#include <bitset>
//最轻者先装一定是整体最优解，满足贪心选择
using namespace std;
struct node
{
??? int id;
??? int val;
};
node box[2005];
int n,c;
bool operator <(const node &a,const node &b)
{
??? return a.val<b.val;
}
void greedySelect()
{
??? sort(box,box+n);
??? bitset<2005> b;
??? b.reset();
??? for(int i=0;i<n;i++)
???? if(box[i].val <= c)
???? {
????????? b[box[i].id]=1;
????????? c-=box[i].val;
???? }
???? else break;
???? cout<<b.count()<<endl;
}
int main()
{
??? while(cin>>n>>c)
??? {
??????? for(int i=0;i<n;i++)
??????? {
??????????? box[i].id=i;
??????????? cin>>box[i].val;
??????? }
??????? greedySelect();
??? }
??? return 0;
}
