动态规划：所有咖啡杯变干净的时间

在使用咖啡机制作咖啡时，应确保咖啡杯干净无油渍。 #生活常识# #家用咖啡机#

1、题目

给定一个数组 arr，arr[i] 代表第 i 号咖啡机泡一杯咖啡的时间。

给定一个正数 N，表示 N 个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡。

只有一台洗杯器，一次只能洗一个杯子，时间耗费 a ，洗完才能洗下一杯。

每个咖啡杯也可以自己挥发干净，时间耗费 b，咖啡杯可以并行挥发。

假设所有人拿到咖啡之后立刻喝干净，返回从开始等到所有咖啡杯变干净的最短时间。

三个参数：int[] arr、int N，int a、int b

2、思路

假设有 3 台咖啡机： arr[3] = [3, 1, 7]。

准备一个 小根堆，堆中放置对象：【(咖啡机可以再用的时间，咖啡机泡一杯的时间)】

所以一开始小根堆中会放置的三个对象：(0, 1)，(0,3)，(0, 7)，堆中的排序是 “咖啡机可以再用的时间 + 泡一杯咖啡的时间” 两个因素共同决定的。

0 号客人来了，首先弹出小根堆中 (0,1)，客人拿到咖啡立马喝完，那么现在 0 号咖啡机可以再用的时间就是 1，于是0号咖啡机对应的对象变成 (1,1)，重新放入堆中， 1 + 1 < 0 + 3 1 + 1 < 0 + 3 1+1<0+3，所以此时堆中的对象排序是 (1,1)、(0,3)、(0，7）。 【0 号客人喝完时间：1】

1 号客人来了，小根堆中弹出 (1,1)，所以 0 号咖啡机可以再用的时间就是2，对应的对象就是 (2,1)，该对象重新入堆，此时堆中的排序是(2,1)、(0,3)、(0,7)。【1号客人喝完时间：2】

2 号客人来了，小根堆中弹出 (2,1)，当前的咖啡机再用时间变成3，对应对象(3,1)，重新入堆，此时堆中排序是(0,3)、(3,1)、(0,7)。【2号客人喝完时间：3】

3 号客人来了，小根堆弹出(0,3)，当前咖啡机再用时间变成 0 + 3 = 3，对应对象(3,3)，重新入堆，此时堆中排序是(3,1)、(3,3)、(0,7)。【3号客人喝完时间：3】

… …

人是一股脑涌过来的，但是利用小根堆得出了最优的排队方案。小根堆出队和入队的过程就是模拟了排队的过程。

public class Coffee {public static class Machine {public int timePoint; //咖啡机可再用的时间public int workTime; //咖啡机泡杯咖啡的时间public Machine(int t, int w) {timePoint = t;workTime = w;}} public static class MachineComparator implements Comparator<Machine> { @Overridepublic int compare(Machine o1, Machine o2) {return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);} } public static int minTime(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])); //初始时所有咖啡机都是在0号时间点可用 } //得到每个人的喝完时间 int[] drinks = new int[n];//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); } } 123456789101112131415161718192021222324252627282930313233343536

此时得到了 drinks 数组，该数组是每个人喝完的时间的最优数组。

假设最优数组是 [2 4 9]，如果洗杯器每分钟洗个杯子，而挥发的话需要50分钟。
2 号时间点喝完的杯子，用洗杯器洗，那么在 3 时间点就能洗完；
4 号时间点喝完的杯子，用洗杯器洗，在 5 时间点就能洗完；
9 号时间点喝完的杯子，用洗杯器洗，在 10 时间点就能洗完。
如果选择挥发需要用时 50 min，就太夸张了。
这种情况下，所有人的杯子都用洗杯器洗是最优的。

但是假设有 4 台咖啡机，每台泡咖啡的时间都是 [3,3,3,3]，而洗杯器洗一个杯子的时间是 2 min，挥发的时间是 5 min。
那么在 3 号时间点来了 4 个杯子需要洗，所以如果都用洗杯器洗的话，全部洗完的时间是 3 + 4 × 2 = 11 3 + 4 \times 2 = 11 3+4×2=11。
但是如果全部选择挥发，那么 3 + 5 = 8 就能结束。

上述两种情况是单纯地选择用洗杯器洗或者挥发，但是可能存在更复杂的情况，既用洗杯器又挥发，这是存在选择的。

在做出的两种选择中，选择时间最少的那个，就是要求的答案。

//drinks：所有杯子开始洗的时间 //wash：洗杯器洗完一杯的时间（串行） //air：自然挥发的时间（并行） //index：当前来到第index号人的杯子 //free：洗杯器什么时间可用 //返回drinks[index...] 从index开始所有杯子都变干净，最早的结束时间 public 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; //index杯子自身变干净的时间点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); //因为之前的杯子没用洗杯器，所以洗杯器可用的时间还是freeint p2 = Math.max(selfClean2, restClean2);return Math.min(p1, p2); } 1234567891011121314151617181920212223

贪心+优良暴力版本（Java 版）

所以完整代码：

public class Coffee {public static class Machine {public int timePoint; //咖啡机可再用的时间public int workTime; //咖啡机泡杯咖啡的时间public Machine(int t, int w) {timePoint = t;workTime = w;}} public static class MachineComparator implements Comparator<Machine> { @Overridepublic int compare(Machine o1, Machine o2) {return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);} } // 优良一点的暴力尝试的方法 public static int minTime(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])); //初始时所有咖啡机都是在0号时间点可用 } //得到每个人的喝完时间 int[] drinks = new int[n];//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.....]都变干净，最早的结束时间（返回）public 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);} } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556

递归函数 bestTime 中有两个可变参数 index 和 free，index 的变化范围 0~n，而 free 的变化范围不知道。这就是业务限制模型。

【业务限制模型：可变参数不能直观地得到变化范围】

这时，就要人为地想限制，将 free 的变化范围估出来。

free 的最大值就是所有杯子都去洗，能到达的最大的值。【限制不够，业务来凑】

修改为动态规划：

动态规划版本 （Java版）

public class Coffee {public static class Machine {public int timePoint; //咖啡机可再用的时间public int workTime; //咖啡机泡杯咖啡的时间public Machine(int t, int w) {timePoint = t;workTime = w;}} public static class MachineComparator implements Comparator<Machine> { @Overridepublic int compare(Machine o1, Machine o2) {return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);} } public static int minTime(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])); //初始时所有咖啡机都是在0号时间点可用 } //得到每个人的喝完时间 int[] drinks = new int[n];//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, 0, 0); } public static int bestTimeDp(int[] drinks, int wash, int air) { int n = drinks.length; int maxFree = 0; for (int i = 0; i < drinks.length; i++) { //估出free的最值 maxFree = Math.max(maxFree， drinks[i]) + wash; } int[][] dp = new int[n + 1][maxFree + 1]; //递归函数中，index依赖于index+1，所以上边行依赖底下行，于是从下往上填。 //dp[n][...] = 0 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) { //超过maxFree的这个状态肯定到不了,因为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]; } } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566

Java 版对数器

public class Code03_Coffee {// 验证的方法// 彻底的暴力// 很慢但是绝对正确public static int right(int[] arr, int n, int a, int b) {int[] times = new int[arr.length];int[] drink = new int[n];return forceMake(arr, times, 0, drink, n, a, b);}// 每个人暴力尝试用每一个咖啡机给自己做咖啡public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {if (kth == n) {int[] drinkSorted = Arrays.copyOf(drink, 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, forceMake(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);}// for testpublic static int[] randomArray(int len, int max) {int[] arr = new int[len];for (int i = 0; i < len; i++) {arr[i] = (int) (Math.random() * max) + 1;}return arr;}// for testpublic static void printArray(int[] arr) {System.out.print("arr : ");for (int j = 0; j < arr.length; j++) {System.out.print(arr[j] + ", ");}System.out.println();}public static void main(String[] args) {int len = 10;int max = 10;int testTime = 10;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int[] arr = randomArray(len, max);int n = (int) (Math.random() * 7) + 1;int a = (int) (Math.random() * 7) + 1;int b = (int) (Math.random() * 10) + 1;int ans1 = right(arr, n, a, b);int ans2 = minTime1(arr, n, a, b);int ans3 = minTime2(arr, n, a, b);if (ans1 != ans2 || ans2 != ans3) {printArray(arr);System.out.println("n : " + n);System.out.println("a : " + a);System.out.println("b : " + b);System.out.println(ans1 + " , " + ans2 + " , " + ans3);System.out.println("===============");break;}}System.out.println("测试结束");} } 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889

C++ 完整版

/*************************************************************************> File Name: 070.coffee.cpp> Author: Maureen ************************************************************************/ #include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; //纯暴力 class Coffee1 { private: vector<int> copyOf(vector<int> &drink, int n) { vector<int> copy(n); for (int i = 0; i < n; i++) { copy[i] = drink[i]; } return copy; } public: int forceWash(vector<int> &drinks, int a, int b, int index, int washLine, int time) { if (index == drinks.size()) return time; //选择1：当前index号咖啡杯，选择用洗杯器洗干净 int wash = max(drinks[index], washLine) + a; int ans1 = forceWash(drinks, a, b, index + 1, wash, max(wash, time)); //选择2：当前index号咖啡杯，选择挥发 int dry = drinks[index] + b; int ans2 = forceWash(drinks, a, b, index + 1, washLine, max(dry, time)); return min(ans1, ans2); } //每个人暴力尝试用每个咖啡机给自己做咖啡 int forceMake(vector<int> &arr, vector<int> &times, int kth, vector<int> &drink, int n, int a, int b) { if (kth == n) { vector<int> drinksSorted = copyOf(drink, kth); sort(drinksSorted.begin(), drinksSorted.end()); return forceWash(drinksSorted, a, b, 0, 0, 0); } int time = INT_MAX; for (int i = 0; i < arr.size(); i++) { int work = arr[i]; int pre = times[i]; drink[kth] = pre + work; times[i] = pre + work; time = min(time, forceMake(arr, times, kth + 1, drink, n, a, b)); drink[kth] = 0; times[i] = pre; } return time; } //验证方法 int right(vector<int> &arr, int n, int a, int b) { vector<int> times(arr.size()); vector<int> drink(n); return forceMake(arr, times, 0, drink, n, a, b); } }; //贪心 + 优良暴力 class Coffee2 { public: class Machine { public: int timePoint; int workTime; Machine(int t, int w) : timePoint(t), workTime(w) {} }; struct CMP { bool operator()(Machine* const &m1, Machine* const &m2) { return m1->timePoint + m1->workTime > m2->timePoint + m2->workTime;//小根堆 } }; int minTime(vector<int> &arr, int n, int a, int b) { priority_queue<Machine *, vector<Machine*>, CMP> que; for (int i = 0; i < arr.size(); i++) { que.push(new Machine(0, arr[i])); } vector<int> drinks(n); for (int i = 0; i < n; i++) { Machine *cur = que.top(); que.pop(); cur->timePoint += cur->workTime; drinks[i] = cur->timePoint; que.push(cur); } return bestTime(drinks, a, b, 0, 0); } int bestTime(vector<int> &drinks, int wash, int air, int index, int free) { if (index == drinks.size()) return 0; //index 号杯子选择洗 int selfClean1 = max(drinks[index], free) + wash; int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1); int p1 = max(selfClean1, restClean1); //index 号杯子选择挥发 int selfClean2 = drinks[index] + air; int restClean2 = bestTime(drinks, wash, air, index + 1, free); int p2 = max(selfClean2, restClean2); return min(p1, p2); } }; //贪心 + 优良暴力 改写为 动态规划 class Coffee3 { public: class Machine { public: int timePoint; int workTime; Machine(int t, int w) : timePoint(t), workTime(w) {} }; struct CMP { bool operator()(Machine* const &m1, Machine* const &m2) { return m1->timePoint + m1->workTime > m2->timePoint + m2->workTime; } }; int minTime(vector<int> &arr, int n, int a, int b) { priority_queue<Machine*, vector<Machine*>, CMP> que; for (int i = 0; i < arr.size(); i++) { que.push(new Machine(0, arr[i])); } vector<int> drinks(n); for (int i = 0; i < n; i++) { Machine *cur = que.top(); que.pop(); cur->timePoint += cur->workTime; drinks[i] = cur->timePoint; que.push(cur); } return bestTimeDp(drinks, a, b); } int bestTimeDp(vector<int> &drinks, int wash, int air) { int n = drinks.size(); int maxFree = 0; for (int i = 0; i < n; i++) { maxFree = max(maxFree, drinks[i]) + wash; } int dp[n + 1][maxFree + 1]; memset(dp, 0, sizeof(dp)); /*vector<vector<int> > dp(n + 1, vector<int>(maxFree + 1)); for (int i = 0; i < maxFree + 1; i++) { dp[n][i] = 0; }*/ for (int index = n - 1; index >= 0; index--) { for (int free = 0; free <= maxFree; free++) { int selfClean1 = max(drinks[index], free) + wash; if (selfClean1 > maxFree) break; //index 号杯子选择洗 int restClean1 = dp[index + 1][selfClean1]; int p1 = max(selfClean1, restClean1); //index号杯子选择挥发 int selfClean2 = drinks[index] + air; int restClean2 = dp[index + 1][free]; int p2 = max(selfClean2, restClean2); dp[index][free] = min(p1, p2); } } return dp[0][0]; } }; vector<int> randomArray(int len, int max) { vector<int> arr(len); for (int i = 0; i < len; i++) { arr[i] = rand() % max + 1; } return arr; } void printArray(vector<int> &arr) { cout << "arr : "; for (int j = 0; j < arr.size(); j++) { cout << arr[j] << ", "; } cout << endl; } int main() { int len = 10; int max = 10; int testTime = 10; cout << "测试开始" << endl; for (int i = 0; i < testTime; i++) { vector<int> arr = randomArray(len, max); int n = rand() % 7 + 1; int a = rand() % 7 + 1; int b = rand() % 10 + 1; Coffee1 *c1 = new Coffee1(); Coffee2 *c2 = new Coffee2(); Coffee3 *c3 = new Coffee3(); int ans1 = c1->right(arr, n, a, b); int ans2 = c2->minTime(arr, n, a, b); int ans3 = c3->minTime(arr, n, a, b); if (ans1 != ans2 || ans2 != ans3) { printArray(arr); cout << "n : " << n << endl; cout << "a : " << a << endl; cout << "b : " << b << endl; cout << ans1 << ", " << ans2 << ", " << ans3 << endl; cout << "==================" << endl; break; } //cout << i << " time test passed!" << endl; } cout << "测试结束" << endl; return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247

3、技巧

两个技巧：

可变参数估计不出来，拿业务最差情况估计；

关心哪些位置是不需要的，不需要填。

网址：动态规划：所有咖啡杯变干净的时间 https://www.yuejiaxmz.com/news/view/930734

相关内容

木纹咖啡杯
喝完咖啡咖啡垢难清理？教你4个清理咖啡垢小妙招，轻松清洗干净
咖啡空间运营商业计划书
去除杯子里、衣服上的咖啡渍有妙招!
去除杯子里、衣服上的咖啡渍有妙招！
咖啡奶茶培训学校，学习时间规划指南
【日本咖啡杯优惠】哪里买日本咖啡杯便宜,性价比高的日本咖啡杯推荐
奶茶是咖啡因大户： 一杯=4杯咖啡！
去这34家咖啡馆，用本旧书免费换杯咖啡 中国咖啡网
咖啡壶与杯：器物美学中的生活哲学

随便看看