Table of Contents
1. Venue arrangement issues
1. Algorithm overview
2. Code
2. Optimal service order problem
1. Algorithm overview
2. Code
3. Virtual car refueling problem
1. Algorithm overview
2. Code
4. Optimal decomposition problem
1. Algorithm overview
2. Code
1. Venue Arrangement Issues
1. Algorithm Overview
Venue scheduling problem: Suppose you want to arrange a batch of events in enough venues, and hope to use as few venues as possible. Design an effective greedy algorithm to schedule. (In fact, it is a derivative of the previous event arrangement problem)
Algorithm: The greedy algorithm is first sorted by the end time. The difference from the activity scheduling is that every time the activity scheduling problem is calculated, a venue must be added, and there is no need to calculate this activity again.
Parameters Table:
s[ ]: activity start time
f[ ]: activity end time
exist[ ]: Whether the current venue is in use, 1 if used, 0 if not in use
room[ ]: room[0] calculates the number of venues, room[1] calculates the number of currently unexecuted activities, if it is 0, exit the traversal.
2. Code
import java.util.Scanner;
//Venue arrangement issues
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) & amp; & amp;(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 is the reference position
temp = arr[low];
while (i<j) {
while (temp<=arr[j] & amp; & amp;i<j){j--;}; //Decrease the right sentinel by one
while (temp>=arr[i] & amp; & amp;i<j){i + + ;}; //Add one to the left sentinel
if (i<j) { //Exchange
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
t = s[j];
s[j] = s[i];
s[i] = t;
}
}
arr[low] = arr[i]; //Exchange the numbers whose reference is equal to i and j
arr[i] = temp;
int tmp_s=s[low];s[low]=s[i];s[i]=tmp_s;
quickSort(arr, s,low, j-1); //recursively call the left half of the array
quickSort(arr,s, j + 1, high); //recursively call the right half of the array
}
}
Test case:
//Input 5 1 23 12 28 25 35 27 80 36 50 //Output 3
2. Optimal service order problem
1. Algorithm Overview
Optimal service order problem: There are n customers waiting for a service at the same time. The service time required by customer i is
Algorithm: Greedy algorithm. Since n customers start waiting at the same time, the starting time is 0 and the service time is 
Average waiting time=![\sum_{i=0}^{arr.length-1} arr[i]*(n-i)](http://i2.wp.com/latex.csdn.net/eq?\sum_{i=0}^{arr.length-1}arr[i]*(n-i))
2. Code
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);
}
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<j) {
while (temp<=arr[j] & amp; & amp;i<j){j--;};
while (temp>=arr[i] & amp; & amp;i<j){i + + ;} ;
if (i<j) {
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);
}
3. Virtual car refueling problem
1. Algorithm Overview
Virtual car refueling problem: A virtual car can travel nkm after being filled with fuel. There are k gas stations during the journey. The distance between the starting point, adjacent gas stations, and the end point is given. All points are collinear. Design an algorithm. , point out which gas stations to stop for refueling, minimize the number of refuelings along the way, and generate an optimal solution.
Algorithm: Greedy algorithm, you only need to determine whether the car’s fuel tank can still drive over this distance, otherwise refuel immediately. If it can drive over this distance, there is no need to refuel.
2. Code
//Car refueling problem
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;
}
}
4. Optimal decomposition problem
1. Algorithm Overview
Optimal decomposition problem: Suppose n is a positive integer. Now we need to decompose n into the sum of several different natural numbers, and the product of these natural numbers is the largest.
Algorithm: Greedy algorithm. The greedy aspect of this question is very clever. It is called halving. If the number n is an odd number, the two middle numbers will be multiplied to the maximum value. If n is an even number, the middle number will be divided into n-n/2. The product of the maximum values of points is the maximum value. In fact, the internal overlapping effect of sub-problems is somewhat similar to dynamic programming.
There is this property in integer decomposition: if a + b = const, then the smaller |a – b|, the larger a·b.
=\begin{Bmatrix}\left\lfloor\frac{x}{2}\right\rfloor\times(\left\lfloor\frac{x}{2}\right\rfloor+1)\qquad\quadx$\%$2==0\\left\lfloor\frac{x}{2}\right\rfloor\timesbestdivide(\left\lfloor\frac{x}{2}\right\rfloor\quadx$\%$2\
eq0)\end{Bmatrix})
2. Code
import java.util.Scanner;
import java.util.ArrayList;
//Optimal decomposition problem
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;
}
}
}
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56903 people are learning the system