c - 马车抢劫(C语言)

Question

晚上好。如果问题格式不正确，我深表歉意，因为这是我第一次在这里发帖。

我正在寻求特定练习的帮助，因为我已经集思广益了近两个小时，但找不到任何合适的解决方案。练习如下:给定一定数量的货车，两个小偷将争夺最高的利润。

第一个小偷，假设是 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;
}

Answer 1

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

对于小偷 B 的所有可能策略，您必须找到小偷 A 的最佳得分

对于小偷 A 的每一步，计算小偷 B 的最佳策略，并选择 A 的最小化策略。迭代。