gpt4 book ai didi

algorithm - 无法理解动态规划

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:42:21 27 4
gpt4 key购买 nike

<分区>

昨晚我有一个关于动态规划的作业,但我不得不把它未完成,因为我不明白如何解决最后一个问题:

The state wants to monitor traffic on a highway n miles long. It costs ci to install a monitoring device on mile i of the highway. The maximum distance between monitoring devices should not be more than d miles. That is, if there is a monitoring device on mile i, then there must be one monitoring device from mile i + 1 to mile i + d (or it is the case that i + d > n). The state wants a plan that will minimize the cost. Assume there is an array C[1..n] of costs.

Let vk be the cost of the best solution assuming a k mile highway and assuming a monitoring device on mile k. Given C and d, if the values of v1 through vk-1 are known, show how to determine the value of vk. You can write this mathematically, or provide pseudocode in the style of the book. Note you need to take into account all possible values of k from k = 1 to k = n.

我确信在即将到来的考试中会出现与此类似的问题,我想至少知道从哪里开始解决这个问题,因此我们将不胜感激。

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com