2

金盒问题（方法）

有“n”个金盒子排成一排，每个盒子都有不同数量的金币。

2名玩家玩游戏，目的是收集最大数量的金币。每个玩家都可以看到每个盒子里有多少硬币，但只能在轮到他的时候从任一端得到一个盒子。设计一个让玩家 1 获胜的策略（假设两个玩家都玩得很聪明）

这个问题在亚马逊的一次采访中被问到。我尝试了这种方法：

#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 也很聪明。我错过了什么？

4

1 回答 1

0

我得到了解决方案，只是接近了。这是我错过的：

“对手打算选择给用户留下最低价值的硬币。”

这是更新的解决方案：

#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/

于 2014-03-22T14:25:20.443 回答