KTV最优点歌策略问题算法分析与研究

刁 航，金昕怡

（1.东北林业大学信息与计算机工程学院，黑龙江 哈尔滨 150040；2.东北林业大学机电工程学院，黑龙江 哈尔滨 150040）

日常生活中，在时间有限、选择有限的情况下，经常需要选择最优策略使利益最大化。所谓最优策略，指在相同约束条件下能尽最大可能满足要求的策略。KTV唱歌是一种常见的娱乐项目，点歌时在价格固定的前提下会有唱歌时长有限、点歌选择有限、歌曲时长不同等问题，就会出现最优点歌策略，即在相同时间下点唱曲目尽可能多、离开KTV时间尽可能晚。关于这类问题的解法多种多样，其中贪心算法、动态规划算法最为常用。贪心算法是一种经过改进后的分级处理方法，其特点是一步一步进行，根据某个优化测度，每一步都要保证能获得局部最优解[1]。贪心算法需要根据题意先行确定一个量度标准，而大多数量度标准下所得的解不一定为问题最优解[2]。动态规划算法的基本思想是将待求解问题分解成若干子问题，并利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解[3]。本文分别采用这两种算法处理问题并进行对比。

1 KT V最优点歌策略问题描述

一般来说，KTV不会在“时间到”的时候鲁莽地把你正在唱的歌曲“切掉”，而是会等它放完。例如，在还有15 s的时候再唱一首2 min的歌曲，则实际上多唱了105 s。但是融合了多首歌曲的《劲歌金曲》《情歌王》等歌曲时长超过10 min，如果唱这种歌曲，相当于多唱了超过600 s。……