c - 货车抢劫(C语言)

晚上好。如果问题的格式不正确，我感到很抱歉，因为这是我第一次在此处发布。

我正在寻求特定运动的帮助，因为我已经进行了近两个小时的头脑风暴，找不到合适的解决方案。
练习如下：给定一定数量的货车，两个小偷将争夺最高利润。

第一个小偷，比如说A，首先开始采摘。小偷可以选择列表上当前可用的第一个或最后一个旅行车。然后从列表中删除选择的货车，并将其值添加到该小偷的计数器中。练习的目的是为小偷A获得最大可能的利润，同时还要确保小偷B试图这样做。

例如，如果有以下输入：

6
10
150
3
7
9
9

这意味着有6个旅行车，其值分别为10、150、3、7、9和9。如果遵循最佳策略，则假设两个盗贼都遵循最佳策略，则输出应为166。但是，到目前为止，我设法获得的全部是169，从理论上讲，无论贼B的游戏方式如何，贼A都能获得的最高结果。

我没有看到如何确保两个盗贼都遵循最佳策略的代码方式。应该说这是一个练习，您必须检查所有可能的组合，但是我如何查看结果并找出两个盗贼遵循的最佳策略？有任何想法吗？

代码：

#include <stdio.h>
#include <stdlib.h>

#define DEBUG 0

int max = 0;
int diff = 9999;

int heist(int *wagons, int i, int j, int carry, int turn, int pos){
    #if DEBUG
    printf("DEBUG! i: %d || j: %d || carry: %d || turn: %d || post: %d || max: %d\n",i,j,carry,turn,pos,max);
    #endif
    /* Stopping condition */
    if (i==j){
        if (turn) carry += wagons[i];
        if (carry>=max){
            max = carry;
        }
        return 0;
    }
    if (!pos){
        /* First wagon */
        if (turn) carry += wagons[i];
        i++;
    } else {
        /* Last wagon */
        if (turn) carry += wagons[j];
        j--;
    }
    turn = !turn;
    heist(wagons,i,j,carry,turn,0);
    heist(wagons,i,j,carry,turn,1);
    return 0;
}

int main()
{
    /* Variables */
    int n;
    scanf("%d",&n);
    if (!n){
        printf("0\n");
        return 0;
    }
    int wagons[n];
    int i;
    /* Inputs */
    for (i=0;i<n;i++){
        scanf("%d",&wagons[i]);
    }
    heist(wagons,0,n-1,0,1,0);
    heist(wagons,0,n-1,0,1,1);
    printf("%d\n",max);
    return 0;
}

最佳答案

您的算法将探索所有可能性，并为小偷A计算最大结果。如果小偷B使用了最差的策略，您会为小偷A获得最高的分数也就不足为奇了。

您必须为小偷B的所有可能策略找到最佳的小偷A分数

对于小偷A的每个举动，计算小偷B的最佳策略，然后按A选择最小化的举动。重复。

关于c - 货车抢劫(C语言)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28658355/