目录

1.活动安排

任务描述

输入格式

输出格式

输入样例

输出样例

代码实现

2.最优装载

任务描述

输入格式

输出格式

输入样例

输出样例

代码实现

3.背包问题

任务描述

输入格式

输出格式

输入样例

输出样例

代码实现

4.会场安排

任务描述

输入格式

输出格式

输入样例

输出样例

代码实现

5.删数问题

任务描述

输入格式

输出格式

输入样例

输出样例

代码实现

1.活动安排

任务描述

学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。

输入格式

第一行是一个整数n(1 随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)

输出格式

输出安排的最多的活动数

输入样例

11
1 4
3 6
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

输出样例

4

代码实现

#include
void change(int &m,int &n){
     int temp=n;
     n=m;
     m=temp;
 }
 void sort(int time[][2],int n){
     for(int j=n-1;j>0;j--){
     for(int i=0;itime[i+1][1]){
             change(time[i][0],time[i+1][0]);
             change(time[i][1],time[i+1][1]);
            }//按结束时间排序，选择越早结束的活动，才可以安排更多的活动 
        }
    }
 }
 int main(){
     int n;
     int count=1;
     int first;
     scanf("%d",&n);
     int time[n][2];
     for(int i=0;i=time[j][1]){
            count++;
            j=i;
        }
    }
    printf("%d",count);
    return 0;
 }

2.最优装载 任务描述

有一天，海盗截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一但打碎就失去了价值，虽然海盗船足够大，但载重量为C，每件古董的重量为Wi，海盗们如何把尽量多的宝贝装上海盗船呢？

输入格式

第一行输入n，c，代表有n个古董和船的重量
第二行输入n个数，代表每个古董的重量。
1 每个古董的重量不超过100

输出格式

输出一个数，代表最多装多少个古董

输入样例

8 30
4 10 7 11 3 5 14 2

输出样例

5

代码实现

 #include
void change(int &m,int &n){
     int temp=n;
     n=m;
     m=temp;
 }
 void sort(int x[],int n){
     for(int j=n-1;j>0;j--){
     for(int i=0;ix[i+1]){
             change(x[i],x[i+1]);
            }//按重量排序，先选择越轻，才可以装载的更多 
        }
    }
 }
 int main(){
     int c,n;
     int count=0;
     scanf("%d %d",&n,&c);
     int x[n];
     for(int i=0;i 
 
3.背包问题 
任务描述 
现在有很多物品（它们是可以分割的）,每个物品有多个，我们知道它们每个物品的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
 
输入格式 
第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数w,v。
 
输出格式 
输出每组测试数据中背包内的物品的价值和，每次输出占一行。
 
输入样例 
3 15
 5 10
 2 8
 3 9
 
输出样例 
60
 
代码实现 
 
 
#include
void change(int &m,int &n){
     int temp=n;
     n=m;
     m=temp;
 }
 void sort(int wv[][2],int n){
     for(int j=n-1;j>0;j--){
     for(int i=0;i 
 
4.会场安排 
任务描述 
　　假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)
 
输入格式 
第一行有1 个正整数k，表示有k 个待安排的活动。接下来的k 行中，每行有2 个正整数，分别表示k 个待安排的活动开始时间和结束时间。时间以0 点开始的分钟计。
 
输出格式 
将编程计算出的最少会场数
 
输入样例 
5 1 23
 12 28
 25 35
 27 80
 36 50
 
输出样例 
3
 
代码实现 
 
 
 #include
 int main(){
     int k;
     int count=0;
     int j=0;
     scanf("%d",&k);
     int a[k];
     int b[k];
      for(int i=0;i 
 
 
5.删数问题 
任务描述 
有一个长度为n（n <= 240）的正整数，从中取出s（s < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。
 
输入格式 
第一行输入n和s
 
输出格式 
输出一个整数
 
输入样例 
178543 4
 
输出样例 
13
 
代码实现 
 
 
 #include
 #include
 //思想：每次找出序列中从前往后升序的最后一个，降序的第一个去除
 int main(){
     int s;
     char n[240];
     scanf("%s %d",&n,&s);
    int length=strlen(n); 
     for(int i=0;in[j+1]){
                for(int m=j;m