签约棒球运动员

假设你是一支棒球大联盟球队的总经理。在赛季休季期间,你需要签入一些自由球员。球队老板给你的预算为X美元,你可以使用少于X美元来签入球员,但如果超支,球队老板就会解雇你。

你正在考虑在N个不同位置签入球员,在每个位置上,有P个该位置的自由球员供你选择。由于你不希望任何位置过于臃肿,因此每个位置最多签入一名球员(如果在某个特定位置上你没有签入任何球员,则意味着计划继续使用现有球员)。

阅读全文

库存规划

Rinky Dink公司是一家制造溜冰场冰面修整设备的公司。这种设备每个月的需求量都在变化,因此公司希望设计一种策略来规划生产,需求是给定的,即它虽然是波动的,但是是可预测的。公司希望设计接下来的$n$个月的生产计划。

对第$i$个月,公司知道需求$d_i$,即该月能够销售出去的设备的总量。令$D=\sum_{i=1}^{n}d_i$
为后$n$个月的总需求。公司雇佣的全职员工,可以提供一个月制造$m$台设备的劳动力。如果公司希望一个月内制造多于$m$台的设备,可以雇佣额外的兼职劳动力,雇佣的成本为每制造一台机器付出$c$美元。而且,如果在月末还有设备未售出,公司将付出库存成本。

阅读全文

基于接缝裁剪的图像压缩

给定一幅彩色图像,它由$m\times n$的像素$A[1\cdots m,1\cdots n]$构成,每个像素是一个红绿蓝$(RGB)$亮度的三元组。假定我们希望轻度压缩这幅图像。具体地,我们希望从每一行中删除一个像素,使得图像变窄一个像素。

为了避免影响视觉效果,我们要求删除的像素必须位于同一列或者是相邻列,也就是说,删除的像素构成从底端到顶端的一条“接缝”(seam),相邻像素均在垂直或对角线方向上相邻。

阅读全文

投资策略规划

你所掌握的算法知识帮助你从Acme计算机公司获得了一份令人兴奋的工作,签约奖金为1万美元。你决定利用这笔钱进行投资,目标是10年后获取最大回报。你决定请Amalgamated投资公司管理你的投资,该公司投资回报规则如下:

阅读全文

字符串拆分

字符串拆分概论

某种字符串处理语言能够允许程序员将一个字符串拆分成为两段。由于此操作需要复制字符串,因此需要$n$个时间单位来将一个$n$个字符串拆分为两段。假定一个程序员希望将一个20个字符的字符串在第2个,第8个,以及第10个字符串进行从左到右拆分。

阅读全文

译码算法

我们可以通过在有向图$G=(V,E)$中使用动态规划的算法来实现语音识别功能。
对每条边$(u,v) \in E$打上一个声音标签$\sigma (u,v)$,该声音来自于有限声音集$\sum$ 。图中从特定的顶点$v_0 \in V$开始的每条路径都对应模型产生一个可能的声音序列。对于一条有向路径,我们定义标签为路径中边的标签的简单连结。

阅读全文

公司聚会计划

公司内部结构关系是层次化的,即员工按主管—下属关系构成一棵树,根节点为公司主席。人事部按“宴会交际能力”给每个员工打分,分值为实数。
Stewart教授是一家公司总裁的顾问,这家公司正在计划一个公司的聚会。这个公司有一个层次式的结构;也就是,管理关系形成一颗以总裁为根的树。人事部门按每个员工喜欢聚会的程度来排名,排名是一个实数。为了使每个参加聚会者都喜欢这个聚会,总裁不希望一个雇员和她的直接上司同时参加。

Stewart教授面对一颗描述公司结构的树,使用了左孩子右兄弟描述法。树中每个节点除了包含指针,还包含雇员的名字以及雇员喜欢聚会的排名。描述一个算法,它生成一张客人列表,使得客人喜欢聚会的程度的总和最大。分析你的算法的执行时间。

最大喜欢程度和?

阅读全文

整齐打印与编辑距离问题

整齐打印

使用等宽字符打印一段文本。输入文本为n个单词的序列,单词长度为$l_1,l_2, \cdots l_n$个字符,将其打印在若干行上,每一行最多$Maxnum$个字符。
如果某行包含第$i$到第$j(i \leq j)$个单词,行尾额外空格符的数量是$M-j+i-\sum_{k=i}^jl_k$,这个值必须是非负的。

阅读全文

回文子序列与欧几里德旅行商

回文子序列

最长回文子序列是正序与逆序相同的非空字符串。例如,所有长度为1的字符串,civic,racecar,aibobphobia都是回文。设计算法,求给定输入字符串的最长回文子序列。例如,给定输入character,算法应该返回carac。算法的运行时间是怎么样的?

阅读全文