晚上好。如果问题格式不正确,我深表歉意,因为这是我第一次在这里发帖。
我正在寻找特定练习的帮助,因为我已经集思广益了将近两个小时,但找不到任何合适的解决方案。练习如下:给定一定数量的货车,两个小偷将争夺最高的利润。
第一个小偷,比方说 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;
}