假设你还想去巴黎,因此在前述清单中又添加了几项。

去这些地方游览需要很长时间,因为你先得从伦敦前往巴黎,这需要半天时间。如果这3个地方都去玩,是不是要4.5天呢?

不是的,因为不是去每个地方都得先从伦敦到巴黎。到达巴黎后,每个地方都只需1天时间因此玩这3个地方需要的总时间为3.5天(半天从伦敦到巴黎,每个地方1天),而不是4.5天。

将埃菲尔铁塔加入“背包”后,卢浮宫将更“便宜”:只要1天时间,而不是1.5天。如何使用动态规划对这种情况建模呢?

没办法建模。动态规划功能强大,它能够解决子问题并使用这些答案来解决大问题。 但仅当每个子问题都是离散的,即不依赖于其他子问题时,动态规划才管用。 这意味着使用动态规划算法解决不了去巴黎玩的问题。

results matching ""

    No results matching ""