计算图遍历中的行程数
计算图遍历中的行程数
提问于 2018-02-10 19:24:24
你好，堆栈溢出社区，
我正试图解决这个问题：problem&problem=1040
问题是如何根据边间的容量来寻找最佳路径。我知道这可以用动态规划来解决，我对它们提供的例子感到困惑：
根据问题描述，如果有人试图让99人从城市1到7，路线应该是1-2-4-7，因为每条边沿的重量代表了可以同时到达的乘客的最大数量。我不明白的是，描述说它至少需要5次旅行。5是从哪里来的? 1-2-4-7是3跳，如果我这次旅行我计算出4次旅行，因为25是路线上最有限的一次，我会说你需要99/25或者至少4次。这是打错了，还是我漏掉了什么？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-02-10 23:51:20
考虑到问题陈述的第一行：
G.先生做导游。
很可能，G先生必须总是在公共汽车上，因此，旅行次数的公式是：
x = (ceil(x) + number_of_passengers) / best_route而不是简单地：
x = number_of_passengers / best_route或者，对于你的数字：
x = (ceil(x) + 99) / 25这些问题可以通过以下方式解决：
x == 4.16 (trips)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48724706
复制相关文章
相似问题
腾讯云开发者
