甜品店切蛋糕问题(动态规划,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语言实现代码:

package main



import (

        "fmt"

)



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

func smin(n int32) int32 {

        if n&1 == 0 {

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

        }

        return (n - 1) / 2 * n

}



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

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

        for i := range lenght {

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

        }

}



/*求二者最大值*/

func maxInt32(a, b int32) int32 {

        if a > b {

                return a

        }

        return b

}



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

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

        if i == 0 {

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

                        return 1

                }

                return 0

        }

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

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

        }

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

}



/*求最后结束时间*/

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

        var max, tmp int32 = 0, 0

        for i := range r {

                tmp = r[i] + s[i]

                if max < tmp {

                        max = tmp

                }

        }

        return max

}



func main() {

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

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

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

        s := make([]int32, 4)

        serverTime(s, length, 4)

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

}

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2016-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

面向对象编程的正确姿势

计算机程序=数据结构+算法。这是大学 C 语言教材里非常经典的一句话。这也道出了计算机程序的本质,即通过对一定的数据结构用相应的算法(逻辑)进行处理从而解决用户...

11520
来自专栏互联网杂技

用于数学的 10 个优秀编程语言

作为一个对数学和编程语言充满激情的人,谁也不能阻止我分享我总结的10个超棒的用于数学的编程语言。 正文共:2619 字 预计阅读时间:7 分钟 作为一个对数学...

553100
来自专栏机器之心

观点 | 为什么我对MATLAB情有独钟

选自Medium 作者:Christopher Madan 机器之心编译 参与:路雪、黄小天 本文作者 Christopher Madan 喜欢用 MATLAB...

399110
来自专栏算法与数据结构

蓝桥杯:兰顿蚂蚁

问题描述 ?   兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。   平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一...

34260
来自专栏牛客网

18届秋招c++面试流水账

18届秋招部分流水账,c++开发方向。供春招参考 定义: - 为回答一般 +为较好 x为不会 【远景能源】【挂】 1面 笔试,手写一个编程题。剑指offer原题...

41680
来自专栏杨建荣的学习笔记

Python实现的快速排序

今天看了下《算法新解》这本书,很薄的一本书,最开始吸引我的有两点,一个是里面的大量的图,内容相对来说比较清新,第二个是里面的代码是基于Python实现。尽管算法...

39870
来自专栏程序人生 阅读快乐

《算法心得 高效算法的奥秘 原书第2版》

由在IBM工作50余年的资深计算机专家撰写,Amazon全五星评价,算法领域最有影响力的著作之一

7910
来自专栏华章科技

阿里电话面试(算法工程师)

说起参加阿里巴巴这次内推过程挺有意思的,起因是我写了一篇关于知识图谱的文章:知识图谱相关会议之观后感分享与学习总结,然后有位大哥发私信给我,希望以后多交流并交换...

98320
来自专栏牛客网

阿里巴巴 java 1+2+3+hr面

【每日一语】现在不是去想缺少什么的时候,该想一想凭现有的东西你能做什么。——海明威《老人与海》

13340
来自专栏PPV课数据科学社区

【学习】从入门到精通,我是这样学习算法的

这篇文章讲了什么? 我这些年学习数据结构和算法的总结。 一些不错的算法书籍和教程。 算法的重要性。 初学 第一次接触数据结构是在大二下学期的数据...

37580

扫码关注云+社区

领取腾讯云代金券