0

我想知道应该使用什么策略来解决以下问题。

问题陈述

有 2 个煤矿，每个煤矿雇用一组矿工。我们的工作是将食品运送到矿山。每次一船食物到达他们的矿场，矿工们就会生产一些煤炭。食品运输分为三种类型：肉、鱼和面包。

每次有新货物到达他们的矿山时，他们都会考虑新货物和前两批货物（如果没有那么多，则更少），然后：

  • 如果所有货物的类型相同，它们将生产一单位煤
  • 如果货物中有两种不同类型的食物，它们将生产两个单位的煤。
  • 如果有三种不同类型的食物，他们将生产三个单位的煤。

食品运输的类型和发送顺序是事先知道的。

输入

您会按照发送顺序获得食品运输的类型。

目标

目标是最大化煤炭产量。这是通过确定哪些货物应该去哪个矿山来完成的。2 个矿场不一定要接收相同数量的货物（实际上，允许将所有货物发送到一个矿场）。

例子

对于装运订单：MBMFFB，预期产量（最大可能的煤炭产量）为 12。

4

1 回答 1

1

您使用的逻辑是错误的：

M -> Mine 1 = 1 coal unit(s)

B -> Mine 1 = 2 "

M -> Mine 2 = 1 "

F -> Mine 1 = 3 "

F -> Mine 2 = 2 "

B -> Mine 2 = 3 "

因为第一天，我的 1 只有一种食物。

我可以看到一个简单的动态规划算法，但我会把它留给你。

一个简单的提示：对于每批货物，您可以将其发送到矿井 1 或矿井 2；发送后，重要的是：

  1. 已开采的矿量；
  2. 前 3 批货物。

因此，最多有 (3 ^ 3) ^ 2 = 729 种装运配置，并且每种配置都有最佳的煤量。在每一步计算这些配置，最后你会得到答案。

于 2013-07-11T15:34:03.520 回答