甜品店切蛋糕问题（动态规划，Go语言实现）_切蛋糕的最小代价编程题

问题重现：
小Y最近在甜品店工作,其工作是切蛋糕。现在有n个顾客来购买蛋糕，并且每个顾客有一个到达的时间，以及需要买的蛋糕的长度ai。由于小Y每次只能服务一个顾客，【问题严谨性补充：而顾客如果进店没有服务员立刻为他服务，他将离开】所以对于相冲突的顾客没有办法提供服务。问小Y最多能为多少位顾客提供服务。小Y能够决定是否卖蛋糕给某个顾客。如果答应顾客要买长度为ai的切糕，那么小Y还要将蛋糕切成单位长度给顾客。如果对ai的蛋糕切成x和ai-x，所花的时间代价为x*(ai-x)。例如，当一个用户在1时刻，需要长度为4的蛋糕，此时小Y可以将其先切成2分长度为2的，花费为4，再将两段长度为2的分别切成1,1的，花费分别为1和1，则总花费时间为4+1+1 = 6， 则小Y为该用户服务时间为6.

已知第i位顾客进店时间，以及购买蛋糕大小。

分析:
涉及问题一：大小为n的蛋糕需要多长时间切成单位长度？

f(x)=x*(n-x) 绘制函数草图可以得到：x=1时得到最小值，也就是说每次1单位1单位的切

用数学归纳法证明上述的解得到的最终和解也是最小的
n=2时 f(x)显然得到的最小解
n=3时 f(x)显然得到的最小解
n=4时 f(x)显然得到的最小解
...
假设n=i-1时也能得到最小解
n=i时
切成x 和(i-x)
显然x必然是前面已经推出的n的一个解，i-x也是前面推出的一个解，而f(x)的最优解和f(i-x)就是每次1单位1单位的切
这时只要保证x*(i-x)值最小即可，最小情况x=1，也就证明了每次1单位1单位的切的解得到的最终和解也是最小的。

涉及问题二：已知各位顾客的进店时间和购买蛋糕大小，如何选出最佳服务对象？

这个问题至少可以使用贪心策略来解决，似乎包含了动态规划，看起来很像01背包问题

动态规划：
f[t]表示t时间内在前i个人已服务完的服务对象人数
s表示第i个人需要的服务时长
r表示第i个人达到时间点

㈠对于是否选择服务第i个人有两种情形
①选择，但要满足完成第i人的服务后时间不超过t
（如果选择了第i个人，可能就存在不允许选前i-1个人中的某些人）
f[t]=f[i-1][r]+1 【t>=r+s】
②不选，不改变在t时间的策略
（之所以不选的原因，就是因为第i个人到时，小Y还没有为前面的人服务完，又或者如果选了第i人会耽误后面更多的人）
f[t]=f[i-1][t]
㈡决策退出条件（决策既知条件）
时间没有负数,所以无需判断
i==0 返回1或0  
解释：因为i==0即最后一个人，如果满足条件t >= r[0]+s[0],返回1
㈢决策入口条件
t=max{s+r}

于是可以得出：
状态转移方程为：f[t]=max{ f[i-1][t-s] (t>=r+s),
f[i-1][t]}

以下给出Go语言实现代码：

1. package main
   

2. 
   

3. import (
   

4. "fmt"
   

5. )
   

6. 
   

7. /*求最小服务时长，每次1单位1单位的切，得到的是最小解*/
   

8. func smin(n int32) int32 {
   

9. if n&1 == 0 {
   

10. return (n / 2) * (n - 1)
    

11. }
    

12. return (n - 1) / 2 * n
    

13. }
    

14. 
    

15. /*求每个顾客的时间*/
    

16. func serverTime(s, lenght []int32, maxLen int32) {
    

17. for i := range lenght {
    

18. s[i] = smin(lenght[i])
    

19. }
    

20. }
    

21. 
    

22. /*求二者最大值*/
    

23. func maxInt32(a, b int32) int32 {
    

24. if a > b {
    

25. return a
    

26. }
    

27. return b
    

28. }
    

29. 
    

30. /*DP问题核心 作者：天之 CSDN博客：http://blog.csdn.net/WAPWO?viewmode=contents*/
    

31. func dptz(i, t int32, r, s []int32) int32 {
    

32. if i == 0 {
    

33. if t >= r[0]+s[0] {
    

34. return 1
    

35. }
    

36. return 0
    

37. }
    

38. if t >= r[i]+s[i] {
    

39. return maxInt32(dptz(i-1, r[i], r, s)+1, dptz(i-1, t, r, s))
    

40. }
    

41. return dptz(i-1, t, r, s)
    

42. }
    

43. 
    

44. /*求最后结束时间*/
    

45. func endTime(r, s []int32) int32 {
    

46. var max, tmp int32 = 0, 0
    

47. for i := range r {
    

48. tmp = r[i] + s[i]
    

49. if max < tmp {
    

50. max = tmp
    

51. }
    

52. }
    

53. return max
    

54. }
    

55. 
    

56. func main() {
    

57. //蛋糕长度、先来后到的时间和服务时间
    

58. length := []int32{2, 2, 3, 4}
    

59. r := []int32{5, 5, 6, 10}
    

60. s := make([]int32, 4)
    

61. serverTime(s, length, 4)
    

62. fmt.Println(dptz(3, endTime(r, s), r, s))
    

63. }