一台咖啡机arr[i],N个人等待泡咖啡，咖啡机洗杯子耗时a,自己挥发耗时b,返回从开始等到所有咖啡杯变干净的最短时间

心已赠人 2022-10-11 00:52 101阅读 0赞

问题描述：给出一个数组arr，arr\[i\]代表第i号咖啡机泡一杯咖啡的时间;整数N,表示N个人等着咖啡机，每台咖啡机只能轮流泡咖啡，假如只有一台洗咖啡杯的机器，一次只能洗一个杯子，时间耗费a,洗完才能洗下一杯；每个咖啡杯也可以自己挥发干净，耗时b，咖啡杯可以并行挥发，假如所有人拿到咖啡之后立刻喝完，则返回从开始等到所有咖啡杯变干净的最短时间；

四个参数为：int\[\] arr，int N，int a ，int b

解决方案：暴力递归到动态规划

1、性能最低的暴力递归：

1.1、核心代码

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**
     * @author wanghuainan
     * @date 2021/7/1 14:37
     */
    public class NanDaoCoffee {
    
        public static void main(String[] args) {
            int[] arr = {7, 2};
            int n = 2;
            int a = 1;
            int b = 8;
            int test1 = leastTime1(arr, n, a, b);
            int test2 = leastTime2(arr, n, a, b);
            int test3 = leastTime3(arr, n, a, b);
            System.out.println(test1 + " , " + test2 + " , " + test3);
        }
    
        private static int leastTime1(int[] arr, int n, int a, int b) {
            int[] times = new int[arr.length];//每个人都用这台机器，时间总和
            int[] drink = new int[n];//所有人依次采用每台咖啡机泡咖啡的时间，比如n个人均使用第arr[i]机器泡咖啡,drink就是每个人的时间叠加比如：三个人都用arr[0]机器，drink就是[7,14,21]
            return forceDo(arr, times, 0, drink, n, a, b);
        }
    
        // 每个人暴力尝试用每一个咖啡机给自己做咖啡
        private static int forceDo(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
            if (kth == n) {
                int[] drinkSorted = Arrays.copyOf(drink, kth);//取不超过kth个数的值，组成新的数组
                Arrays.sort(drinkSorted);//默认是升序
                return forceWash(drinkSorted, a, b, 0, 0, 0);
            }
            int time = Integer.MAX_VALUE;
            for (int i = 0; i < arr.length; i++) {
                int work = arr[i];
                int pre = times[i];
                drink[kth] = pre + work;
                times[i] = pre + work;
                time = Math.min(time, forceDo(arr, times, kth + 1, drink, n, a, b));
                drink[kth] = 0;
                times[i] = pre;
            }
            return time;
        }
    
        public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
            if (index == drinks.length) {
                return time;
            }
            // 选择一：当前index号咖啡杯，选择用洗咖啡机刷干净
            int wash = Math.max(drinks[index], washLine) + a;
            int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));
    
            // 选择二：当前index号咖啡杯，选择自然挥发
            int dry = drinks[index] + b;
            int ans2 = forceWash(drinks, a, b, index + 1, washLine, Math.max(dry, time));
            return Math.min(ans1, ans2);
        }
    
    }

2、优化后的暴力递归：

2.1、流程图所示：

2.2、核心代码：

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**
     * @author wanghuainan
     * @date 2021/7/1 14:37
     */
    public class NanDaoCoffee {
    
        public static void main(String[] args) {
            int[] arr = {7, 2};
            int n = 2;
            int a = 1;
            int b = 8;
            int test1 = leastTime1(arr, n, a, b);
            int test2 = leastTime2(arr, n, a, b);
            int test3 = leastTime3(arr, n, a, b);
            System.out.println(test1 + " , " + test2 + " , " + test3);
        }
    
         
        // 以下为贪心+优良暴力
        public static class Machine {
            public int timePoint;
            public int workTime;
    
            public Machine(int t, int w) {
                timePoint = t;
                workTime = w;
            }
        }
    
    
        // 好点的暴力尝试方法
        private static int leastTime2(int[] arr, int n, int a, int b) {
            //设置自定义小根堆
            PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
            for (int i = 0; i < arr.length; i++) {
                heap.add(new Machine(0, arr[i]));
            }
            int[] drinks = new int[n];
            for (int i = 0; i < n; i++) {
                Machine cur = heap.poll();
                cur.timePoint += cur.workTime;
                drinks[i] = cur.timePoint;
                heap.add(cur);
            }
            return bestTime(drinks, a, b, 0, 0);
        }
    
        // drinks 所有杯子可以开始洗的时间
        // wash 单杯洗干净的时间（串行）
        // air 挥发干净的时间(并行)
        // free 洗的机器什么时候可用
        // drinks[index.....]都变干净，最早的结束时间（返回）
        private static int bestTime(int[] drinks, int wash, int air, int index, int free) {
            if (index == drinks.length) {
                return 0;
            }
            // index号杯子 决定洗
            int selfClean1 = Math.max(drinks[index], free) + wash;
            int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
            int p1 = Math.max(selfClean1, restClean1);
    
            // index号杯子 决定挥发
            int selfClean2 = drinks[index] + air;
            int restClean2 = bestTime(drinks, wash, air, index + 1, free);
            int p2 = Math.max(selfClean2, restClean2);
            return Math.min(p1, p2);
        }
    
        public static class MachineComparator implements Comparator<Machine> {
    
            @Override
            public int compare(Machine o1, Machine o2) {
                return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
            }
    
        }
    
         
    }

3、标准动态规划方案：

3.1 、流程图所示：

3.2、核心代码：

import java.util.Arrays;
    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**
     * @author wanghuainan
     * @date 2021/7/1 14:37
     */
    public class NanDaoCoffee {
    
        public static void main(String[] args) {
            int[] arr = {7, 2};
            int n = 2;
            int a = 1;
            int b = 8;
            int test1 = leastTime1(arr, n, a, b);
            int test2 = leastTime2(arr, n, a, b);
            int test3 = leastTime3(arr, n, a, b);
            System.out.println(test1 + " , " + test2 + " , " + test3);
        }
     
        // 贪心+优良尝试改成动态规划
        public static int leastTime3(int[] arr, int n, int a, int b) {
            PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
            for (int i = 0; i < arr.length; i++) {
                heap.add(new Machine(0, arr[i]));
            }
            int[] drinks = new int[n];
            for (int i = 0; i < n; i++) {
                Machine cur = heap.poll();
                cur.timePoint += cur.workTime;
                drinks[i] = cur.timePoint;
                heap.add(cur);
            }
            return bestTimeDp(drinks, a, b);
        }
    
        public static class MachineComparator implements Comparator<Machine> {
    
            @Override
            public int compare(Machine o1, Machine o2) {
                return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
            }
    
        }
    
    
        private static int bestTimeDp(int[] drinks, int wash, int air) {
            int N = drinks.length;
            int maxFree = 0;
            for (int i = 0; i < drinks.length; i++) {
                maxFree = Math.max(maxFree, drinks[i]) + wash;
            }
            int[][] dp = new int[N + 1][maxFree + 1];
            for (int index = N - 1; index >= 0; index--) {
                for (int free = 0; free <= maxFree; free++) {
                    int selfClean1 = Math.max(drinks[index], free) + wash;
                    if (selfClean1 > maxFree) {
                        break; // 因为后面的也都不用填了
                    }
                    // index号杯子 决定洗
                    int restClean1 = dp[index + 1][selfClean1];
                    int p1 = Math.max(selfClean1, restClean1);
                    // index号杯子 决定挥发
                    int selfClean2 = drinks[index] + air;
                    int restClean2 = dp[index + 1][free];
                    int p2 = Math.max(selfClean2, restClean2);
                    dp[index][free] = Math.min(p1, p2);
                }
            }
            return dp[0][0];
        }
    
    }

到此，三种方案分享完毕，稍微不足的地方是，没有给大家提供详细的图表，莫急，我近期正在思考，等有结果了，一定给大家及时提供，敬请期待！