algorithm - 基于价格的酒店房间优化分配

Question

这不是一道作业题。这是我们在构建在线产品时面临的问题。希望有人能告诉我这是否是一般算法问题。

假设我有4个房间的配置:
第一间 - 2人 - 800
第二间- 3人- 1400
第三间 - 2人 - 1000
第 4 间 - 2 人 - 2000

假设我想以最低成本容纳 4 人。那么理想情况下我应该得到第一个房间 + 第三个房间

我尝试使用价格/人来解决它，但是会失败，因为它会给出第一个房间和第二个房间的输出

请说出正确的算法来解决这个问题

Answer 1

正如理查德在评论中正确指出的那样，这类似于背包。但是，很容易适应 pseudo-polynomial dynamic programming solution from it .

假设您有 n 个房间和 m 个人。创建一个长度为 m + 1 的向量 C，元素初始化为 P[i] = ∞ for i > 0，并且 P[0] = 0。 C 的第 i 个条目包含找到的最佳选项，至少可以容纳 i 人。

现在执行三重循环:

• 遍历每个房间。假设当前考虑的房间可以容纳 p 人，费用为 c。

  • 对于每个 i = 0, ..., m

    • 对于每个 j = i, ..., min(m, i + p)

      • 更新 P[j] = min(P[j], P[i] + c)

检查 P[m] 以获得最佳解决方案的成本。

假设这里所有的数学成本都是恒定的，这具有复杂性Θ(n m²)。

---

找到最佳房间集，而不仅仅是它们的总成本，基本上是一样的。在向量中，添加两个额外的条目:一个用于更新条目的最后一个房间，一个用于更新此条目的最后一个条目。