甜品店切蛋糕问题(动态规划,Go语言实现)

abv123456789 · · 2581 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

问题重现:
小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. import (

  3. "fmt"

  4. )


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

  6. func smin(n int32) int32 {

  7. if n&1 == 0 {

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

  9. }

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

  11. }


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

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

  14. for i := range lenght {

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

  16. }

  17. }


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

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

  20. if a > b {

  21. return a

  22. }

  23. return b

  24. }


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

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

  27. if i == 0 {

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

  29. return 1

  30. }

  31. return 0

  32. }

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

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

  35. }

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

  37. }


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

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

  40. var max, tmp int32 = 0, 0

  41. for i := range r {

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

  43. if max < tmp {

  44. max = tmp

  45. }

  46. }

  47. return max

  48. }


  49. func main() {

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

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

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

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

  54. serverTime(s, length, 4)

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

  56. }


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:abv123456789

查看原文:甜品店切蛋糕问题(动态规划,Go语言实现)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2581 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传