最大利润-备忘录法，动态规划，最优性

Question

最大利润-备忘录法，动态规划，最优性

algorithm

3

我在练习算法游戏中的问题，尝试了下面的问题，但找不到有效的解决方法：

所以你能帮助我吗？以下是问题链接：

这是精确的链接：http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm228

- user1134599

我无法高效地解决这个问题，尽管我阅读了许多关于博弈论/策略游戏的教程，还参考了这个网站http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames，但仍然无法产生想法... - user1134599

1

@mshsayem 这与问题有些无关：除非你知道一种特定的技巧，否则你的尝试几乎肯定会偏离轨道，不能为进一步讨论提供有效的起点。 - Sergey Kalinichenko

@mshsayem：我无法正确启动，尝试了暴力破解，但对于N≥100来说速度变得非常慢。有什么方法可以解决这个问题吗？谢谢！ - user1134599

4个回答

2

让 dp[i, j] = 爱丽丝可以从第i个到第j个硬币中获得的最大利润。

我们有：

dp[i, i] = input[i] for all 1 <= i <= N
dp[i, i + 1] = max(input[i], input[i + 1])
dp[i, j] = max(// take first coin, opponent will minimize your next move
               input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]),
               // take last coin, opponent will still minimize your next move
               input[j] + min(dp[i, j - 2], dp[i - 1, j - 1]))

- IVlad

1

我假设您想自己解决这个问题，因此我会给您一个提示：这个问题具有最优子结构。

想象一下，您已经有了N-1 个硬币的解决方案（没有最左边和最右边的那个）。那么计算N个硬币的解决方案会很容易吗？

您可以使用两种相关技术来利用这个性质 - 动态规划及其子类型记忆化搜索。思路是将每个缺失左侧L枚硬币和右侧R枚硬币的子问题的解决方案存储在一个NxN数组中。在解决子问题之前，请检查数组以查看是否已经解决它。您最多需要解决N^2/2个子问题才能得出解决方案。

以下是记忆化搜索方案的伪代码：

// solved[L][R] array contains the highest value a player could get
// on a subproblem where L coins are missing from the left
// and R are missing from the right of the original sequence on his move
int solved[N][N] // initialize each element to -1.
int coins[N]     // initialize with coin values 

int solve(int L, int R) {
    if (L+R == N) return 0; // No coins remain
    if (solved[L][R] >= 0) return solved[L][R];
    int remaining = sum(coins from L to R)
    int takeLeft = remaining - solve(L+1, R);
    int takeRight = remaining - solve(L, R+1);
    int result = max(takeLeft, takeRight);
    solved[L][R] = result;
    return result;
}

main() {
    int alice = solve(0, 0);
    int bob = sum(coins) - alice;
}

我记得TopCoder在2005年或2006年早期运行过这个问题，但我记不清足够的细节来搜索他们的问题存档。

- Sergey Kalinichenko

谢谢 @dasblinkenlight。您能提供伪代码吗？我不太擅长动态规划，有点难理解。谢谢！ - user1134599

@Jack，我在我的伪代码中修复了一个错误，之前的不正确。 - Sergey Kalinichenko

在理解一些问题时遇到了困难，sum（从L到R的硬币总和）是什么意思？coins.Length（是否指硬币数量为N）是什么意思？ - user1134599

coins.Length 的确为 N。sum(coins from L to R) 是游戏中剩余硬币的总和，即序列左侧缺少 L 枚硬币，右侧缺少 R 枚硬币。我还修复了伪代码中的一个偏移问题。 - Sergey Kalinichenko

1

//@ IVlad ::Implement your code ,its giving incorrect answer.Had I implemented it properly??
int coins[1000];
int dp[1000][1000];
int main()
 {
int T,N;//N=How many coins are there
cin>>T; //No of Test Cases.
while(T--)
{
    cin>>N;
    for(int i=1;i<=N;++i)
    {
        cin>>coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        dp[i][i]=coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        if(i+1<=N)
        dp[i][i + 1] = max(coins[i], coins[i + 1]);
    }
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N;++j)
        {
            if((i+2)<=N && (i+1)<=N && (j-2)>=1 && (i-1)>=1 && (j-1)>=1)
            dp[i][j]=max( (coins[i] + min(dp[i + 2] [j], dp[i + 1][ j - 1])),coins[j] + min(dp[i] [j - 2], dp[i - 1] [j - 1]));
        }
    }
    cout<<dp[1][N]<<endl;//Answer
}

return 0;

}

- user1190601

@IVlad：抱歉忽略了之前的帖子，我错误地实现了您的伪代码。您的解决方案已被接受，谢谢。 - user1190601

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jarosław Gomułka · Accepted Answer

你可以使用动态规划来解决它。状态可以表示为：

set of available coins,
whos turn it is

对于每个状态，您应该计算出每个人可以赢得的最大金额。

提示：这个游戏的规则允许将可用硬币集描述为一个区间。

@编辑

for(int interval_size = 1; interval_size <= n; interval_size++) {
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) {
         // result[interval_start][interval_start + interval_size] depends only on
         // -> result[interval_start][interval_start + interval_size - 1]
         // -> result[interval_start + 1][interval_start + interval_size]
    }
}