假如你是一名新入职的富士康流水线工人 张全蛋 , 负责组装iPhone。
那么iPhone的组装分为n多道工序，需要按照顺序从头做到尾，就可以组装出一台新机。
为了简单起见，假设9道工序，顺序如下：
- 从盒子里拿一片加工好的A13 Bionic CPU (为什么是加工好的？因为芯片生产工艺不在中国:)
- 将A13涂上一些硅脂意思意思
- 从盒子里拿一片加工好的主板，并将A13摁到主板上
- 从盒子里拿一个三摄模块，把主板和三摄放到手机后盖上
- 贴上一块容量非常小并且使用祖传5V2A慢充的电池
- 用一种非常规的螺丝固定主板和机身，确保你用户拆不开
- 贴上一块三星产的AMOLED屏幕
- 屏幕中框强力封胶，确保你用热风枪加热都打不开
- 试着亮屏，只要没爆炸就算品控过关，放到包装盒里
先把终极的问题抛出来:
假设整个富士康在iPhone流水线上有m个工人，假设每个工人的效率都是一样的低，那么对于每道工序需要的时间就是一样的，将工序i给一个工人做需要的时间记作A[i]。
比如流水线上一共有3个工人，做上述的9道工序，那么可能步骤8强力封胶需要1分钟，其他12345679都只要10秒钟意思意思。
工作的分配就比较灵活了，可以是以下几种情况
- 一个人只做一道工序
- 一个人做好几道工序
- 几个人一起做一道工序，这时候需要的时间线性除以人数
- 几个人一起做好几道工序，这时候需要的时间线性除以人数
反正做完之后传给做下一道工序的人就可以了。
比如李小花做了第一道工序之后就传给了张全蛋，张全蛋做完2和3之后传给了赵铁柱和他的同事，赵铁柱小组10个人做了剩余的456789。
工人脑容量有限，记不住那么多步骤，对于每一道工序I需要的记忆空间为B[I]，每个工人脑容量相等，为G。G有可能大于sum(B[i])，也有可能小于。
比如步骤7贴屏幕对技术要求有点高，记住这个步骤怎么做就意味着其他的步骤做不了了
在做完一道工序之后，传给下一个工人是需要时间的，并且每道工序的成品传输成本都不一样，将它们记作 C[i]。
比如第二步之后涂完硅脂的A13芯片可能需要小心运输，传给下一个人需要5分钟，而如果已经到第8步了，那么传输就比较方便，三秒钟把手机扔给下一个工人就完事了
成功生产S台iPhone之后需要所有人停下来给这些iPhone装箱，假设这个装箱过程固定时间T_sync
那么问题来了！
给定n道工序的时间代价A[], 工序需要的记忆容量B[], 工序间的传输代价C[], 每批S个iPhone一定要做一次耗时T_sync装箱，那么怎么安排这些m个脑容量为G的工人使得富士康生产iPhone的速度最快呢？
仔细想一下的话会发现这个规划问题非常的复杂，会涉及到各种情况的trade-off，并且想要使用一个简单高效的DP算法解这个问题并不是很直观。
这破问题我来尝试循序渐进地讲一下可能的解法。这一篇(一)先解决一下简化版的问题，年底左右再更新两篇讲上述Final问题的高效解法。
问题 Ver.0 热身
你张全蛋今天第一天上班，领导派你把整个生产线一个人练习一下，需要多少时间？
这个应该不难发现是 \sum_{i=1}^n A[i]吧，如果这个有困难的话这篇文章当故事看好了。
老板发现你只喜欢做其中一部分，于是派你专门只练习生产过程的一部分，工序a到b
那么这个时间消耗就是 \sum_{i=a}^b A[i]
问题 Ver.1
现在我们假设有k个工人在这个iPhone生产线上工作，为了问题简单起见我们先不考虑多个工人同时并行做某一道或多道工序的情况，并且假设工人之间足够近传输元件随便抛，所以传输时间忽略不计。以及暂时不考虑S个iPhone需要装箱的问题，假设这个生产线无限制的一直运行下去、
那么现在需要解决的问题就是怎么把这n道工序分成k份使得流水线的吞吐速度最快的问题了。
因为组装一台iPhone的总的工作量是确定不变的，k个人分工做这些工作，直觉上讲把这n道工序尽可能平均的分到每个工人上(也就是每个工人完成他负责的部分时间跟大家都差不多)的时候流水线效率会是最高的，因为每个工人都忙着。但是这个”分得均匀”或者”时间都差不多”是非常难在算法中定义的。
再仔细想想的话就会发现，这种持续运行的流水线系统的速度取决于k个工人中相对速度最慢的那一位，如果把那个工人的工作稍微分一些给其他人的话整个系统的速度就会相应变快。
那么也就是说我们需要找到n道工序的流水线分给k个工人之后，k个工人工作量的最大值，并且通过调整切分使得这个最大值尽可能小。
问题抽象
给定一列数字共n个，想把它们分成k段，每一分段单独求和，使得这k个和中的最大值尽可能小。
要求只能切成k份，并且切割不能改变原数组的顺序。输出最大分段和的最小值，暂时先不要求输出切分。
举一个例子：
数组 A=[1,4,2,3,5], n = 5, k = 3
显然满足条件的最优切分为[1, 4] [2, 3] [5]，其和的最大值为5
那么其他可能的切分可以是 [1] [4, 2] [3, 5]，这时候和的最大值就是3+5=8了
解法一: 暴力搜索
最简单的想法就是我可以暴力枚举所有可能的k-1个切分位置，并且分别求出他们分段和的最大值，从中找一个最小的出来。对于数组中的每一个元素，我们都可以将它拼接到之前的子数组中，或者切分还没超过k的情况下将它建立为一个新的子数组。代码实现如下:
代码实现
本文所有代码默认包含以下头文件定义
#include <bits/stdc++.h> using namespace std;
int partition(vector<int> A, int n, int k)
{
if (k == 1)
return accumulate(A.begin(), A.begin()+n, 0);
if (n == 1)
return A[0];
int best = INT_MAX;
for (int j=1; j<=n; j++)
best = min(best, max(partition(A, j, k-1), accumulate(A.begin()+j, A.begin()+n, 0)));
return best;
}时空复杂度
该算法的时间复杂度为O(n^k)，因为为了穷举所有可能的split，我们需要遍历{n-1 \choose k-1}次，数量级上为O(n^k)。空间复杂度为O(n)，用于存放数组。
解法二: 动态规划
观察上面的代码，不难发现在做穷举的时候绝大多数计算都是重复的，并且这个问题满足最优子结构性质，所以我们可以尝试使用动态规划的思想来解这个问题。
定义dp[i][j]为将原数组A的前i+1项(A[0…i])分为j份之后的最大数组分段和的最小值。
对于第j个子数组，我们可以考虑改子数组的起点p，用表达式max(dp[p][j-1], A[p+1] + … + A[i]来表示。其中k可以从0到i，相当于对于最后一个子数组做了一次遍历。
该DP算法的状态转移方程: dp[i][j] = min{max{dp[i][1]-dp[p][1],dp[p][j-1]}}
代码实现
int partition(vector<int>& nums, int k) {
int n = nums.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
vector<int> sub(n + 1, 0);
for (int i = 0; i < n; i++) {
sub[i + 1] = sub[i] + nums[i];
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
for (int p = 0; p < i; p++) {
dp[i][j] = min(dp[i][j], max(f[p][j - 1], sub[i] - sub[p]));
}
}
}
return dp[n][k];
}时空复杂度
时间复杂度为O(n^2*k)。这个DP算法总的状态数为O(n*k)，然后在计算每一个状态的时候都需要遍历n次用于找最优的起点p。
空间复杂度为O(n*k)，用于记录所有的状态。
解法三: 二分查找
这个解法相比前两个就是一个paradigm shift了。
与其说不断穷举切分再去算最大分段和的最小值，我们可以尝试直接试出这个最大分段和的最小值。一旦我们固定一个值S作为分段和的最大值，那么接下来要做的就是按顺序将数组一个一个的放进这个容量为S的容器中，一旦发现某个元素放进去之后容器内的和会超过容量，那么就新开一个容器。
对于一个固定的流水线，我们知道它总的工作量Q，一旦确定这个分段和的最大值S，那么需要多少个容量为S的容器也就确定了，是Q/P向上取整。
对于想要试出值的S，它一定不会大于流水线的总工作量，也就是S<=Q=sum(A)。它的下界不会小于每个工人的平均工作量，也就是S>=(Q/k)=(sum(A)/k)。于是就可以通过二分查找的方式，在(Q/k)和Q之间不断尝试S的值，直到收敛。算法实现如下:
代码实现
int partition(vector<int>& nums, int m) {
LL l = 0, r = 0;
int n = nums.size();
for (int i = 0; i < n; i++) {
r += nums[i];
if (l < nums[i]) {
l = nums[i];
}
}
LL ans = r;
while (l <= r) {
LL mid = (l + r) >> 1;
LL sum = 0;
int cnt = 1;
for (int i = 0; i < n; i++) {
if (sum + nums[i] > mid) {
cnt ++;
sum = nums[i];
} else {
sum += nums[i];
}
}
if (cnt <= m) {
ans = min(ans, mid);
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}时空复杂度
时间复杂度为O(n*log(sum(A)))。二分查找的复杂度为O(log(sum(A))，需要对数组做n次。
空间复杂度为O(n)，用于存放原数组。
在原数组数据方差不是特别离谱的情况下这个二分查找的方法是最高效的，同时空间复杂度也只需要一个数组的量。
问题进化 Ver.2
加入考虑进传输代价，但是仍然不考虑记忆代价以及多个工人并行合作的情况。
问题进化 Ver.3
考虑传输代价，多个工人并行合作同一组工序，但是仍不考虑记忆代价限制。
问题 Ver.2, 3, 4, 以及文章开头的Final，解法我倒是已经有了，年底左右再写两篇”最小化数组分段和问题(二)和(三)“把算法和代码都理清楚。
Leave a comment