案例描述:
- Gekko教授想横穿NorthDarkota州, 教授在起点带着两公升水, 在喝光水之前能滑行m英里. 他还携带了一份路线图, 上面标明了沿途补水点距离起点的距离. 试求出教授如何以最少取水次数完成旅程的最优方案(给出所真正要取水的点)
输入: m(一次补水后最大续航里程), s[num], L(总路程长度);
输出: B[count]数组, count为路程中取用水的次数, B[i]为第i次取水的点距离起点的路程;
算法设计:
(1) 最优子结构: 从第i个补水点(和起点的距离为s[i])到终点的最优方案是C(i), 那么C(i)是由我这次在最大续航里程范围内(s[i], s[i]+m]所选取的点k, 以及从k点出发的最优方案C(k)组成;
(2) 写出递归式: C(i) = 1 + C(k) , 附带约束条件s(k) <= s(i)+m;
当然了, 也要考虑下边际条件, 那就是临近终点的情况, 此时:
if s(i) + m >= L, 那么C(i) = 1;
(3) 贪心选择: 每次我尽量让教授走得远, 使得最大续航里程被尽量耗完, 减少补水次数;
也就是让C(i) = 1 + C(k)中的取得满足约束条件情况下的最大值;
证明该贪心策略会生成最优解:
如果教授不选择可续航范围(s(i), s(i)+m]上最远的点的话, 而是通过选择s(k)<=s(greedy)的k点就可以生成最优解,
那么, 就有从i取水点开始往前走的最优解为C(i) = 1+C(k) = 1+ 1 + C(t), t点落在(s(k), s(k)+m], 且关系s(i)<s(k)<s(greedy)<s(k+m)<s(greedy+m)恒成立
但是教授如果改选了更远的greedy点的话,
(1) 要么他仍然可以选择到下一个子问题最优解所选的点, 因为t点落在了[s(greedy), s(k)+m]范围内, 因此他选greedy后, 仍然能继续选择t点, 也同样生成了最优解.
(2) 要么就是greedy点甚至已经比t点还要远了, 因为t点落在了(s(k), s(greedy)), 即满足了s(k)<s(t)<s(greedy)<s(k)+m, 那么此时教授就节省下了一次取水点, 也就是说C(i) = 1+C(greedy) < 1 + 1 + C(t), (s(t) < s(greedy)), 我们获得了比原先最优解更好新的最优解;
综上, 贪心策略总是生成了最优解;
写出算法.
/*取水问题贪心算法-迭代写法*/
GetWater(m, S[num], L)
let B[] be a new array, and B[0] = 0;
j = 0;
for i = 0~num-1
if (S[i] - B[j] > m)
j++;
B[j] = S[i-1];
if (L - S[i] <= m) //尾部的处理;
B[++j] = S[i];
return B[];
时间复杂度显然是O(n), 此处n就是输入的S[num]的元素个数num.
