文章目录

• 一：最优服务次序问题
• • 1.问题描述
  • 2.代码
• 二：删数问题
• • 1.问题描述
  • 2.代码
• 三：最优分解问题
• • 1.问题描述
  • 2.代码
• 四：多机调度问题
• • 1.问题描述
  • 2.代码

一：最优服务次序问题

1.问题描述

设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，（1<=i<=n）。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？（平均等待时间是n个顾客等待服务时间总和除以n）

输入：第一行为一个正整数n，表示有n个顾客 第二行为n个正整数，表示n个顾客需要的服务时间
输出：最小平均等待时间。

输入数据：

10（表示顾客数量）
65 12 9 99 1200 324 33 65 99 874（表示n个顾客需要的服务时间）

输出数据：

611.8

2.代码

package suanfa;
import java.util.Arrays;
import java.util.Scanner;
public class suanfa1{
	public static void main(String[] args) {
		System.out.println("请输入顾客的数量：");
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();//获取顾客的人数
		System.out.println("请依次输入各个顾客的服务时间：");
		int[] time = new int[n+1];//用于存储后续输入的顾客服务时间
		for(int i = 1;i<=n;i++)
			time[i] = s.nextInt();
		Arrays.sort(time);//升序排序
		long alltime = 0;//用于记录总的时间
		for(int i = 1;i<=n;i++) {//时间包括正在经历服务的顾客本身
			alltime +=time[i]*(n-i+1);
		}
		System.out.println("最小的平均等待时间："+(double)alltime/n);
	}
}

二：删数问题

1.问题描述

给定一个高精度正整数a, 去掉其中k个数字后按原左右次序将组成一个新的正整数。对给定的a, k寻找一种方案,使得剩下的数字组成的新数最小。

应用贪心算法设计求解 （1） 设计要点 操作对象为n位高精度数，存储在数组a中。
在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。
当k=1时，对于n位数构成的数删除哪一位，使得剩下的数据最小。删除满足如下条件的a[i]：它是第一个a[i]>a[i+1]的数，如果不存在则删除a[n]（最后一位数字，具体实现时请注意下标表示方法）。
当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头开始，删除第2个，依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n-k个数字即可（相当于删除了若干个最右边的数字）。

2.代码

package suanfa;
import java.util.Scanner;
public class suanfa2 {
	 public static int Delete(String a,int k)
	    {
	        StringBuffer sb=new StringBuffer(a+"");//把a转化为字符串
	        int i=0,j=0;
	        for(i=0;i<k;i++)
	        {
	            /*
	            * 若各位数字递增，则删除最后一个数否则删除第一个减区间的数*/
	            for(j=0;j<sb.length()-1&&sb.charAt(j)<=sb.charAt(j+1);j++)
	            {
	            }
	            sb.delete(j,j+1);
	        }
	        return sb.length()==0?0:Integer.parseInt(sb.toString());
	    }
	    public static void main(String[] args)
	    {
	            Scanner in=new Scanner(System.in);
	            String a=in.next();
	            int b=in.nextInt();
	            if(b<=0)
	                System.exit(0);
	            System.out.println(Delete(a,b));
	    }
}

三：最优分解问题

1.问题描述

设n是一个正整数，要求将n分解为若干互不相同的自然数之和，且这些自然数的乘积最大。
输入：正整数n
输出：计算的最大乘积。
如输入10，则输出30.
提示：若a+b的值为一个常量，则a-b的绝对值越小，ab值越大。贪心策略：将n分成从2开始的连续自然数之和，如果最后剩下一个数，则将此数在后项优先的方式下均匀地分给前面各项。

分析： 一个数被分为任意2个为不为一的数都大于等于原数。那就可以根据这条性质去用贪心策略解决问题。 那从2开始，如果能分解出来就要
10-2=8 8-3 =5 5-4=1<4
到了5那里就是我们的判断条件，因为题目要求分解为不相同的自然数，如果被分解的数分出来以后比分解出来的数小，那么就停止分解，因为再分出来的数要么是重复的要么是1

2.代码

package suanfa;
import java.util.Scanner;
public class suanfa3 {
    public static void main(String args[])
    {
        Scanner input=new Scanner(System.in);
        //System.out.println(a);
        //输入要分解的数。
        int a=input.nextInt();
        int b[]=new int [100];//分解时的i，从2开始
        b[0]=2;
        int i=0;
        while (true)
        {   //判断a中剩余的数，是否有递增的b[i]大，如果大那么继续执行下面的
            //如果不大则对剩余的数递减
            if(b[i]>=a)
            { int j=i-1;//剩下的数还未减为0
                while (a>0)
                { //b的最高位++
                    b[j]++;//b回到前一位
                    j--;//a自减
                    a--;//如果b减到第0位再回到最高位
                    if(j<0)
                        j=i-1;
                }
                break;
            }
            a-=b[i]; //a减去b[i]
            b[i+1]=b[i]+1; //b[i+1]为b[i]自增1
            i++;//b的位数++
        }
        int sum=1; //用sum计总值
        for(int j=0;j<i;j++)
        { //总值为b的每位乘积
           sum*=b[j];
        }
        System.out.println(sum); //输出
    }
}

四：多机调度问题

1.问题描述

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。

这个问题是一个NP完全问题，到目前为止还没有一个有效的解法。对于这一类问题，用贪心选择策略有时可以设计出较好的近似算法。
分别采用以下两种贪心策略实现算法求解，对比实验结果，分析哪种贪心策略更适合应用于多机调度问题。 （1）最长处理时间作业优先的贪心选择策略。
（2）最短处理时间作业优先的贪心选择策略。 至少采用两组实验数据进行实验，请参考实验数据一，自己再设计一组实验数据。
实验数据一：7个独立的作业由3台机器加工处理，各作业所需的处理时间为：{2，14，4，6，16，5，3}。
实验数据二：7个独立的作业由4台机器加工处理，各作业所需的处理时间为：{2，14，4，6，16，5，3}。

2.代码

package suanfa;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
 
public class suanfa4 {
	public static class JobNode implements Comparable{
		int id;//作业的标号
		int time;//作业时间
		public JobNode(int id,int time){
			this.id=id;
			this.time=time;
		}
		@Override
		public int compareTo(Object x) {//按时间从大到小排列
			int times=((JobNode)x).time;
			if(time>times) return -1;
			if(time==times) return 0;
			return 1;
		}		
	}
	public static class MachineNode implements Comparable{
		int id;//机器的标号
		int avail;//机器空闲的时间（即机器做完某一项工作的时间）
		public MachineNode(int id,int avail){
			this.id=id;
			this.avail=avail;
		}
		@Override
		public int compareTo(Object o) {//升序排序，LinkedList的first为最小的
			int xs=((MachineNode)o).avail;
			if(avail<xs) return -1;
			if(avail==xs) return 0;
			return 1;
		}
	}
	public static int greedy(int[] a ,int m){
		int n=a.length-1;//a的下标从1开始，所以n（作业的数目）=a.length-1
		int sum=0;
		if(n<=m){
			for(int i=0;i<n;i++)
				sum+=a[i+1];
			System.out.println("为每个作业分别分配一台机器");
			return sum;
		}
		List<JobNode> d=new ArrayList<JobNode>();//d保存所有的作业
		for(int i=0;i<n;i++){//将所有的作业存入List中，每一项包含标号和时间
			JobNode jb=new JobNode(i+1,a[i+1]);
			d.add(jb);
		}
		Collections.sort(d);//对作业的List进行排序
		LinkedList<MachineNode> h=new LinkedList<MachineNode>();//h保存所有的机器
		for(int i=1;i<=m;i++){//将所有的机器存入LinkedList中
			MachineNode x=new MachineNode(i,0);//初始时，每台机器的空闲时间（完成上一个作业的时间）都为0
			h.add(x);
		}
		int test=h.size();
		for(int i=0;i<n;i++){
			Collections.sort(h);
			MachineNode x=h.peek();
			System.out.println("将机器"+x.id+"从"+x.avail+"到"+(x.avail+d.get(i).time)+"的时间段分配给作业"+d.get(i).id);
			x.avail+=d.get(i).time;
			sum=x.avail;
		}
		return sum;
	}
	public static void main(String[] args) {
		//int[] a={0,2,14,4,16,6,5,3};
		int[] a={2,14,4,6,16,5,3};
		int m=3;
		int sum=greedy(a,m);
		System.out.println("总时间为："+sum);
	}
}