0

こんばんは。初めて投稿するので質問の仕方が悪くてすみません。

2 時間近くブレインストーミングを行ったが、適切な解決策が見つからないため、特定の演習に関する支援を探しています。演習は次のとおりです。特定の数のワゴンが与えられた場合、2 人の泥棒が最高の利益を求めて競争します。

最初の泥棒、たとえば A が最初に摘み取りを開始します。泥棒は、リストで現在利用可能な最初または最後のワゴンのいずれかを選択する可能性があります。次に、選択したワゴンがリストから削除され、その値がそれぞれの泥棒のカウンターに追加されます。この演習の目的は、泥棒 A が可能な限り最高の利益を得ると同時に、泥棒 B が同じことをしようとしていることを確認することです。

たとえば、次の入力があるとします。

6
10
150
3
7
9
9

これは、値が 10、150、3、7、9、および 9 のワゴンが 6 台あることを意味します。最適な戦略に従う場合、両方の泥棒が最適な戦略に従うと仮定すると、出力は 166 になります。ただし、これまでのところ、盗賊 B がどのようにプレイしても、盗賊 A が獲得できる最高の結果である 169 しか得られませんでした。

両方の泥棒がコードに関して最適な戦略に従うことを保証する方法がわかりません。考えられるすべての組み合わせをチェックする必要があると思われますが、結果を見て、どちらの泥棒が最適な戦略に従っているかを判断するにはどうすればよいでしょうか? 何か案は？

コード：

#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;
}
4

2 に答える 2

1

アルゴリズムはすべての可能性を調査し、泥棒 A の最大の結果を計算します。泥棒 B が考えられる最悪の戦略を使用した場合、泥棒 A の最高のスコアが得られることは驚くことではありません。

泥棒 B の考えられるすべての戦略について、泥棒 A にとって可能な最高のスコアを見つける必要があります。

泥棒 A の各動きに対して、泥棒 B の最善の戦略を計算し、それを最小化する動きを A によって選択します。繰り返します。

于 2015-02-22T14:14:58.493 に答える
0

両方のプレーが最適であると仮定して、指定された開始位置から両方のプレーヤーのスコアを返す評価関数が必要です。

#include <stdio.h>

#define N 6

const int WAGONS[N] = { 10, 150, 3, 7, 9, 9 };

// note: SCORE is used as output only
void heist (int score[2], const int *wagons, int i, int j, int player)
{
    if (i > j) {
        score[0] = 0;
        score[1] = 0;
    }
    else {
        int score_first[2];
        int score_last[2];

        // calculate outcome when taking the first element
        heist (score_first, wagons, i + 1, j, 1 - player);
        score_first[player] += wagons[i];


        // calculate outcome when taking the last element
        heist (score_last, wagons, i, j - 1, 1 - player);
        score_last[player] += wagons[j];


        // select optimal choice
        if (score_first[player] > score_last[player]) {
            score[0] = score_first[0];
            score[1] = score_first[1];
        }
        else {
            score[0] = score_last[0];
            score[1] = score_last[1];
        }
    }
}

int main ()
{
    int score[2];

    heist (score, WAGONS, 0, N - 1, 0);
    printf("%d, %d\n", score[0], score[1]);

    return 0;
}
于 2016-11-25T16:46:28.887 に答える