最佳适配策略_游戏的最佳策略

我不是女神ヾ 2023-03-05 09:57 87阅读 0赞

最佳适配策略

**Description:**

**描述：**

This is a very popular interview problem to find maximum outcomes in a two player game played in an optimal way. This problem has been featured in interview rounds of Amazon, Microsoft, Salesforce.

这是一个非常受欢迎的面试问题，目的是在以最佳方式进行的两人游戏中找到最大的结果。 在亚马逊，微软，Salesforce的采访回合中都曾提到过此问题。

**Problem statement:**

**问题陈述：**

You are given an array A of size ***N***. The array contains integers and is of even length. The elements of the array represent ***N*** coin of values *x1, x2, ... ,xn*. The rule of game is:

给您一个大小为***N***的数组A。 该数组包含整数，并且具有偶数长度。 数组的元素表示***N个***硬币，分别为*x 1 ，x 2 ，...，x n* 。 游戏规则是：

1.  Each of the players gets alternative turns.
    
    每个玩家都有交替的回合。
2.  In each turn, a player selects either the first or last coin from the row, removes it
    
    在每个回合中，玩家从该行中选择第一个或最后一个硬币，将其删除
3.  permanently, and receives the value of the coin.
    
    并获得硬币的价值。
4.  Both the player plays in an optimal way, i.e., both want to maximize total winning money.
    
    两位玩家都以最佳方式进行游戏，即，双方都希望最大化总赢钱。

You need to determine the **maximum possible amount of money** you can win if you **start the game**.

您需要确定**开始游戏时**可以赢得的**最大金额** 。

Input
        N=4
        Array values:
        10 30 5 8
    
        Output:
        38

**Example:**

**例：**

Number of coins: 4
        Coin values:
        10 30 5 8
    
        To achieve maximum money:
        I will pick up 8 first (Not 10. Think Why?)
        So the row will be:
        10 30 5
        The opponent will pick 10 as that's optimal
        So the row will be:
        30 5
        I will pick 30
        Opponent will get 5
    
        Total my winnings: 8+30=38
        Total opponents winning: 10+5=15

**Explanation:**

**说明：**

The first thing that comes to our mind that we should go for the greedy method. Since we can only pick either first element or last element, let's pick the local best one, i.e., Pick the one which is maximum of first and last element. Let's see whether such a method would be optimal or not.

我们想到的第一件事是，我们应该采用贪婪的方法。 因为我们只能选择第一个元素或最后一个元素，所以我们选择局部最佳元素，即选择第一个和最后一个元素中最大的一个。 让我们看看这种方法是否是最优的。

Let's take the same example,

让我们以同样的例子

Coin values:
        10 30 5 8
    
        To achieve maximum money using greedy approach:
        I will pick up 10 first (maximum of 10 and 8)
        So the row will be:
        30 5 8
        The opponent will pick 30 as that's maximum of 30 and 8
        So the row will be:
        5 8
        I will pick 8
        Opponent will get 5
    
        Total my winnings: 10+8=18
        Total opponents winning: 30+5=35

Is this optimal? I got less money than the opponent. So we can simply choose the local best one ( Answer of Why), we can't go for greedy.

这是最优的吗？ 我的钱比对手少。 所以我们只能选择当地最好的一个(为什么回答)，我们不能贪婪。

Let's check what can be optimal strategy,

让我们检查一下什么是最佳策略，

Say the coins are,

说硬币是，

x1, x2, ..., xi, x(i+1), ..., x(j-1), x(j), ..., xn

Let,

让，

f(i,j)=maximum wiining for me when ith to jth coins are remaining

There at any stage of game  
And it's my turn  
So, I can either pick xi or xj based on the optimal choice.

在游戏的任何阶段  
轮到我了  
因此，我可以根据最佳选择选择x i或x j 。

1.  So If I choose xi , opponent will pick either of x(i+1) or xj leaving me with *minimum(f(i+2,j),f(i+1,j-1))*
    
    因此，如果我选择x i ，则对手将选择x (i + 1)或x j之一，使我得到的*最小值为(f(i + 2，j)，f(i + 1，j-1))*
    
        Opponent choosing x(i+1) corresponds to f(i+2,j)
            Opponent choosing xj corresponds to f(i+1,j-1)
2.  If I choose xj , opponent will pick either of xi or x(j-1) leaving me with *minimum(f(i+1,j-1),f(i,j-2))*
    
    如果我选择x j ，对手将选择x i或x (j-1)中的任一个，使我得到*最小值(f(i + 1，j-1)，f(i，j-2))*
    
        Opponent choosing xi corresponds to f(i+1,j-1)
            Opponent choosing x(j-1) corresponds to f(i,j-2)

So, I will choose xi or xj what gives me maximum.  
so,

因此，我将选择x i或x j给我最大的收益。  
所以，

![optimal strategy for a game step 1][]

Above is the recursion and we need to convert it into Dynamic Programming.

以上是递归，我们需要将其转换为动态编程。

**Problem Solution:**

**问题方案：**

We need a 2D array to store f(i,j)

我们需要一个2D数组来存储f(i，j)

Say, DP\[n\]\[n\] and the result will be DP\[0\]\[n-1\] //maximum winning for coin 0th to nth (all the coins)

假设， DP \[n\] \[n\]的结果将是DP \[0\] \[n-1\] //第0到第n个硬币(所有硬币)的最大获利

**Base case:**

**基本情况：**

If there is only one coin left, there's no choice
            f(i,i)=arr[i] // arr is the array storing coin values in the row
        So,
        for i=0 to n-1
            DP[i][i]=arr[i]   
        END for
    
        If there is only two coin, i.e., xi, x(i+1)
        I will choose the maximum obviously for maximum winning
        for i=0 to n-2
            DP[i][i+1]=arr[i]   
        END for

To fill rest of the Table using the recursion,

要使用递归填充表格的其余部分，

for (int len = 2; len < n; len++) {
            for (int i = 0, j = len; j < n; i++, j++) {
                DP[i][j] = max⁡(a[i] + min⁡(DP[i + 2][j], DP[i + 1][j - 1]),
                    a[j] + min(DP[i + 1][j - 1], DP[i][j - 2]));
            }
        }

**Initial DP table after computing base cases**

**计算基本案例后的初始DP表**

DP\[4\]\[4\] // N=4

DP \[4\] \[4\] // N = 4

![optimal strategy for a game step 2][]

**Filling up the upper triangular matrix**

**填满上三角矩阵**

Len=2

Len = 2

![optimal strategy for a game step 3][]

Len=3

Len = 3

![optimal strategy for a game step 4][]

**C++ implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    int max(int x, int y)
    {
        
        if (x > y)
            return x;
        else
            return y;
    }
    int min(int x, int y)
    {
        
        if (x < y)
            return x;
        else
            return y;
    }
    int MAX_WINNING(vector<int> a, int n)
    {
        
    
        int DP[n][n]; //DP matrix
        memset(DP, 0, sizeof(DP));
        //base case
        for (int i = 0; i < n; i++) {
        
            DP[i][i] = a[i];
            if (i != n - 1) {
        
                DP[i][i + 1] = (a[i] > a[i + 1]) ? a[i] : a[i + 1];
            }
        }
        //filling up table using recusrion
        for (int len = 2; len < n; len++) {
        
            for (int i = 0, j = len; j < n; i++, j++) {
        
                DP[i][j] = max(a[i] + min(DP[i + 2][j], DP[i + 1][j - 1]), a[j] + min(DP[i + 1][j - 1], DP[i][j - 2]));
            }
        }
        //return result
        return DP[0][n - 1];
    }
    int main()
    {
        
        int n, item;
        cout << "Enter number of Coins\n";
        scanf("%d", &n);
        cout << "Enter coin values\n";
        vector<int> arr;
        for (int j = 0; j < n; j++) {
        
            scanf("%d", &item);
            arr.push_back(item);
        }
    
        cout << "Maximum possible winning is: " << MAX_WINNING(arr, n) << endl;
    
        return 0;
    }

**Output**

**输出量**

Enter number of Coins
    4
    Enter coin values
    10 30 5 8
    Maximum possible winning is: 38

> 翻译自: [https://www.includehelp.com/icp/optimal-strategy-for-a-game.aspx][https_www.includehelp.com_icp_optimal-strategy-for-a-game.aspx]

最佳适配策略

[optimal strategy for a game step 1]: /images/20230208/31d07a64c4fe44a9b5b25e12f2030584.png
[optimal strategy for a game step 2]: https://www.includehelp.com/icp/Images/optimal-strategy-for-a-game-2.jpg
[optimal strategy for a game step 3]: /images/20230208/267f0eb3249042f48ea3fd9f6518757f.png
[optimal strategy for a game step 4]: /images/20230208/5e19671c68e04f2bbca1942e36e8fee9.png
[https_www.includehelp.com_icp_optimal-strategy-for-a-game.aspx]: https://www.includehelp.com/icp/optimal-strategy-for-a-game.aspx