如何设计策略和算法的金盒子游戏 [英] How to design strategy and algorithm for gold box game

问题描述

金箱的问题（方法）

有N金盒子放在一排，每个都具有不同数量的金币。 2个玩家玩游戏，这里的动机是收集金币的最大数量。每个玩家可以看到有多少硬币是present在每个盒子，但可以从任一端只有一个箱子，就轮到他。 设计一个策略，使得PLAYER1胜（假设双方球员发挥聪明）

There are ‘n’ gold boxes placed in a row, each having different number of gold coins. 2 players play a game, where the motive is to collect the maximum number of gold coins. Each player can see how many coins are present in each box, but can get a box from either end only, on his turn. Design a strategy such that Player1 wins (Assuming both players play smartly)

这个问题被问在亚马逊的采访。我试过这个方法：

This problem was asked in an amazon interview. I tried this approach:

#include<stdio.h>
int max(int a, int b) {
    return a>b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
    if(i==j) {
        if(turn == 1) return arr[i];
        else return 0;
    }
    if(turn) {
        return max(arr[i] + maxCoins(arr,i+1,j,0),arr[j] + maxCoins(arr,i,j-1,0));
    } else {
        if(arr[i]>arr[j])
        return maxCoins(arr,i+1,j,1);
        else
        return maxCoins(arr,i,j-1,1);
    }
}    
int main() {
    int arr[10] = {6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
    printf("%d\n",maxCoins(arr,0,9,1));
}

但我认为这是不对的，因为player2也发挥巧妙。请帮助我缺少的是什么。

But I think this is not right, as player2 also plays smartly. Kindly help with what I am missing.

推荐答案

我的解决方案，只是接近。以下是我错过了：

I got to the solution, just was close. Here is what I missed:

对手有意选择了硬币这让与最小值的用户。

"The opponent intends to choose the coin which leaves the user with minimum value."

下面是更新的解决方案：

Here is updated solution:

#include<stdio.h>
int max(int a, int b) {
    return a>b?a:b;
}
int min(int a, int b) {
    return a<b?a:b;
}
int maxCoins(int arr[], int i, int j, int turn) {
    int a,b;
    if(i==j) {
        if(turn == 1) return arr[i];
        else return 0;
    }
    if(turn) {
        a = arr[i] +maxCoins(arr,i+1,j,0);
        b = arr[j] + maxCoins(arr,i,j-1,0);
        return max(a,b);
    } else {
        return min(maxCoins(arr,i+1,j,1), maxCoins(arr,i,j-1,1));
    }
}
int main() {
    int arr[4] = {8, 15, 3, 7 };//{6,7,4,1,10,5,4,9,20,8}; //{2,3,4,5,6,7,8,9,10,11};
    printf("%d\n",maxCoins(arr,0,3,1));
}    

这个环节讨论的策略： 的http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

This link discusses the strategy: http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

这篇关于如何设计策略和算法的金盒子游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！