贪心算法（2）--衍生问题

目录

一、会场安排问题

1、算法概述

2、代码

二、最优服务次序问题

1、算法概述

2、代码

三、虚拟汽车加油问题

1、算法概述

2、代码

四、 最优分解问题

1、算法概述

2、代码 

---

一、会场安排问题

1、算法概述

        会场安排问题：假设要在足够多的会场安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算法，进行安排。（其实就是前面的活动安排问题的衍生问题）

        算法：按照结束时间排序优先进行贪心算法，与活动安排不同的点在于，每当计算一次活动安排问题时，就要添加一个会场，之后也不需要再计算这个活动。

        参数表：

                s[ ]：活动开始时间

                f[ ]：活动结束时间

                exist[ ]：当前会场是否使用，使用为1，未使用为0

                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
        {
            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
        {
            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
        {
            if((exist[j]==0)&&(end<=s[j]))
            {
                begin=f[j];
                end=s[j];
                exist[j]=1;
                room[1]-=1;
            }
        }
        room[0]+=1;
   }
   public static void quickSort(int[] arr,int[] s,int low,int high){
        int i=low; int j=high; int temp,t;
        if(low>high){
            return;
        }
        //temp就是基准位
        temp = arr[low];
 
        while (i
            while (temp<=arr[j]&&i//右哨兵减一
            while (temp>=arr[i]&&i//左哨兵加一
            if (i//交换
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
 
                t = s[j];
                s[j] = s[i];
                s[i] = t;
            }
        }       
        arr[low] = arr[i];        //将基准为与i和j相等位置的数字交换
        arr[i] = temp;
        int tmp_s=s[low];s[low]=s[i];s[i]=tmp_s;
        quickSort(arr, s,low, j-1);  //递归调用左半数组
        quickSort(arr,s, j+1, high); //递归调用右半数组
    }
}

测试用例： 

//输入
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
        {
            total+=arr[i]*(n-i);
        }
        System.out.println(total/10);   
   } 
public static void quickSort(int[] arr,int low,int high){
        int i=low; int j=high; int temp,t;
        if(low>high){
            return;
        }
        temp = arr[low];
        while (i
            while (temp<=arr[j]&&i
            while (temp>=arr[i]&&i
            if (i
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }       
         arr[low] = arr[i];        
         arr[i] = temp;
        quickSort(arr, low, j-1);  
        quickSort(arr, j+1, high); 
    }

三、虚拟汽车加油问题

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
        {
            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的拆分的最大值的乘积为最大值。其实内部的这种子问题重叠的效果，有点类似于动态规划。

        整数分解中有这条性质：若 a + b = const，则 |a - b| 越小，a·b越大。

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 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,ArrayListarr)
   {
        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;
            }
        }
   }
}