目录
一、会场安排问题
1、算法概述
会场安排问题：假设要在足够多的会场安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算法，进行安排。（其实就是前面的活动安排问题的衍生问题）
算法：按照结束时间排序优先进行贪心算法，与活动安排不同的点在于，每当计算一次活动安排问题时，就要添加一个会场，之后也不需要再计算这个活动。
下面代码中，添加exist数组，作为当前会场是否使用，若未使用则为0，使用后为1。添加room数组，room[0]计算会场个数，room[1]计算当前未执行的活动个数，若为0则退出遍历。
2、代码
（代码中省略排序过程）
import java.util.Scanner;
//会场安排问题
public class conferencearrangement {
public static void main(String[] args)
{
int n=new Scanner(System.in).nextInt();
int s[]=new int[n];
int f[]=new int[n];
int exist[]=new int[n];
int i;
for(i=0;i<n;i++)
{
String input=new Scanner(System.in).nextLine();
String []numbers=input.split("\\s+");
s[i]=Integer.parseInt(numbers[0]);
f[i]=Integer.parseInt(numbers[1]);
}
quickSort(f,s, 0, n-1);
int room[]={0,n};
while(true)
{
if(room[1]==0)
break;
GreedySelector(s,f,room,exist);
}
System.out.println(room[0]);
}
public static void GreedySelector(int s[],int f[],int room[],int exist[])
{
int begin;int index=999;int end=999;
for(int i=0;i<s.length;i++)
{
if(exist[i]==0)
{
begin=s[i];
end=f[i];
exist[i]=1;
index=i;
room[1]-=1;
break;
}
}
for(int j=index+1;j<s.length;j++)
{
if((exist[j]==0)&&(end<=s[j]))
{
begin=f[j];
end=s[j];
exist[j]=1;
room[1]-=1;
}
}
room[0]+=1;
}测试用例：
//输入
5
1 23
12 28
25 35
27 80
36 50
//输出
3二、最优服务次序问题
1、算法概述
最优服务次序问题：设有n个顾客同时等待一项服务，顾客i需要的服务时间是,应如何安排n个顾客的服务次序才能使平均等待时间达到最小。
算法：贪心算法，由于n个顾客同时开始等待，则开始时间都为0时刻，服务时间为，结束时间为分别为前一个人i的结束时间
加上
。所以我们可以对服务时间排序，让服务时间最短的优先服务。
平均等待时间=，其中arr数组为按服务时间由短到长排序的数组。
2、代码
（省略排序代码）
public static void main(String args[])
{
int n=10;double total=0;
int arr[]={56,12,1,99,1000,234,33,55,99,812};
quickSort(arr, 0, arr.length-1);
System.out.println(arr[0]);
for(int i=0;i<arr.length;i++)
{
total+=arr[i]*(n-i);
}
System.out.println(total/10);
} 三、虚拟汽车加油问题
1、算法概述
虚拟汽车加油问题：一辆虚拟汽车加满油后可行驶nkm，旅途中有k个加油站，给出起点、相邻加油站、终点之间的距离，所有点位都共线，设计一个算法，指出在哪些加油站停靠加油，使沿途加油次数最少，并产生一个最优解。
算法：贪心算法，只需要判断汽车油箱还能不能开过这一段距离，否则立刻加油，如果能开过这一段距离则不需要加油。
2、代码
//汽车加油问题
public class vehiclerefuel {
public static void main(String args[])
{
int n=7;
int k=7;
int arr[]={1,2,3,4,5,1,6,6};
System.out.println(refuel(n,arr));
}
public static int refuel(int n,int arr[])
{
int count=0;
for(int i=0;i<arr.length;i++)
{
if(n>=arr[i])
n-=arr[i];
else
{
n=arr.length;
n-=arr[i];
count+=1;
}
}
return count;
}
}
四、 最优分解问题
1、算法概述
最优分解问题：设n是一个正整数，现在要将n分解为若干互不相同的自然数之和，且这些自然数的乘积最大。
算法：贪心算法，这道题的贪心很巧妙，简称对半分，如果这个数n是奇数，则中间两个数相乘为最大值，若n为偶数，则中间的数与n-n/2的拆分的最大值的乘积为最大值。其实内部的这种子问题重叠的效果，有点类似于动态规划。
2、代码
import java.util.Scanner;
import java.util.ArrayList;
//最优分解问题
public class bestdivide {
public static void main(String[] args)
{
int n=new Scanner(System.in).nextInt();
ArrayList<Integer> arr=new ArrayList<>();
int tot=1;
divide(n,arr);
for(int num:arr)
tot*=num;
System.out.println(tot);
}
public static void divide(int n,ArrayList<Integer>arr)
{
int tmp=0;
while(true)
{
if(n%2!=0)
{
arr.add(n/2);
arr.add(n-n/2);
break;
}
else
{
arr.add(n/2);
n=n/2;
}
}
}
}