algorithm - Hard DP prob pseudocode algorithm

Question

So this is the question:

There’s an actor doing fan meeting who is trying to do free hugs to his fans lined up in a line. He starts at position 0 and there are fans to his right and left. Their position is depicted by both neg and pos number like -3, 5, etc. The ‘utility’ (economics) his fan gains from the hug starts at certain number, say 10, and decreases by 1 per 1 distance he walks. The actor wants to find an algorithm to maximize the utility his fans gain.

For example, the maximum utility the fans at pos 2, 4, 6 with initial utility of 10 can get is 8 + 6 + 4.

The number of fans N can be up to 100 and initial utility M can be up to 10000 (can’t be negative). The fans’ positions are between -10000 to 10000.

Please help solve this q in pseudocode given the initial utility, number of fans and fans’ position.

I somehow cant think of ways to work it through.

标签： algorithmdata-structuresdynamic-programming

Answer 1

dp[r][l][b][i] = 你可以通过访问 r 作为最右边的粉丝，l 作为最左边的粉丝，b 是一个布尔值，表示你是在最右边还是左边， i 是剩余的效用。可能状态的数量是 100 * 100 * 2 * 10000 = 200000000，应该可以在一秒钟内解决。

伪代码：将 2 中的粉丝分开：那些 < 0 和那些 > 0。

solve(left, right, atRight, utility):
    if left < 0 or right > totalFans or utility <= 0:
        return 0
    if dp[left][right][atRight][utility] != None:
        return dp[left][right][atRight][utility]        

    if atRight == true:
        dp[left][right][atRight][utility] = max(solve(left, right + 1, true, utility - distance(right, right + 1)), solve(left + 1, right, false, utility - distance(right, left + 1))) + utility
    else:
        dp[left][right][atRight][utility] = max(solve(left + 1, right, false, utility - distance(left, left + 1)), solve(left, right + 1, true, utility - distance(right + 1, left))) + utility

return dp[left][right][atRight][utility]



answer = max(solve(0, 1, true, initialUtility - distance(0, firstFan at dist > 0)), solve(1, 0, false, initialUtility - distance(0, firstFan at dist < 0)))

您基本上尝试了所有可能性，您的状态是您所在的位置，您已经拥抱的最右边的粉丝，您已经拥抱的最左边的粉丝以及剩余的实用程序。如果最左边的粉丝是 10，这意味着你已经拥抱了最接近 0 的粉丝，即在 pos < 0、第二、第三、第四……直到第 10 位。