Maximum Profit- memoization, DP, Optimalitäts

Question

ich das Problem auf Algorithm Spiele Üben war, versuchte ich folgendes Problem konnte aber nicht den effizienten Weg finden, es zu tun ::

So können Sie bitte me.Here helfen ist das Problem.

Dies ist das genaue link :: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm228

Answer 1

Ich gehe davon aus, dass Sie selbst diese lösen möchte, also werde ich Ihnen einen Tipp geben: dieses Problem optimal substructure hat.

Stellen Sie sich vor, Sie haben beide Lösungen für N-1 Münzen (ohne die linke und ohne die rechte). Wäre es dann einfach, eine Lösung für N Münzen zu berechnen?

Sie können zwei verwandte Techniken verwenden, um diese Eigenschaft - dynamic programming und ihren Subtyp memoization - auszunutzen. Die Idee ist, eine Lösung für jedes Teilproblem mit L Münzen, die von links fehlen und R Münzen fehlt von rechts zu speichern (verwenden Sie ein NxN Array dafür). Bevor Sie ein Unterproblem lösen, überprüfen Sie das Array, um zu sehen, ob Sie es bereits gelöst haben. Sie müssten höchstens N^2/2 Teilprobleme lösen, um zu einer Lösung zu kommen.

Hier ist Pseudo-Code für eine memoized Lösung:

// solved[L][R] array contains the highest value a player could get 
// on a subproblem where L coins are missing from the left 
// and R are missing from the right of the original sequence on his move 
int solved[N][N] // initialize each element to -1. 
int coins[N]  // initialize with coin values 

int solve(int L, int R) { 
    if (L+R == N) return 0; // No coins remain 
    if (solved[L][R] >= 0) return solved[L][R]; 
    int remaining = sum(coins from L to R) 
    int takeLeft = remaining - solve(L+1, R); 
    int takeRight = remaining - solve(L, R+1); 
    int result = max(takeLeft, takeRight); 
    solved[L][R] = result; 
    return result; 
} 

main() { 
    int alice = solve(0, 0); 
    int bob = sum(coins) - alice; 
} 

Ich erinnere mich an TopCoder Anfang 2005 oder 2006 ist dieses Problem einige Zeit laufen, aber ich erinnere mich nicht genug Details, um ihre Problem-Archiv zu suchen.

Answer 2

Sie es dynamic programming mit lösen können. Staat kann dargestellt werden durch:

set of available coins, 
whos turn it is 

Für jeden Zustand sollten Sie maximale Menge des Geldes, die Person wiederum berechnen gewinnen.

Hinweis: Regeln dieses Spiels erlauben es, set of available coins als Intervall zu beschreiben.

@edit

for(int interval_size = 1; interval_size <= n; interval_size++) { 
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) { 
     // result[interval_start][interval_start + interval_size] depends only on 
     // -> result[interval_start][interval_start + interval_size - 1] 
     // -> result[interval_start + 1][interval_start + interval_size] 
    } 
} 

Answer 3

Lassen Sie dp[i, j] = maximum profit alice can make for the coints i, ... j.

Wir haben:

dp[i, i] = input[i] for all 1 <= i <= N 
dp[i, i + 1] = max(input[i], input[i + 1]) 
dp[i, j] = max(// take first coin, opponent will minimize your next move 
       input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]), 
       // take last coin, opponent will still minimize your next move 
       input[j] + min(dp[i, j - 2], dp[i - 1, j - 1])) 

Answer 4

//@ IVlad ::Implement your code ,its giving incorrect answer.Had I implemented it properly?? 
int coins[1000]; 
int dp[1000][1000]; 
int main() 
{ 
int T,N;//N=How many coins are there 
cin>>T; //No of Test Cases. 
while(T--) 
{ 
    cin>>N; 
    for(int i=1;i<=N;++i) 
    { 
     cin>>coins[i]; 
    } 
    for(int i=1;i<=N;++i) 
    { 
     dp[i][i]=coins[i]; 
    } 
    for(int i=1;i<=N;++i) 
    { 
     if(i+1<=N) 
     dp[i][i + 1] = max(coins[i], coins[i + 1]); 
    } 
    for(int i=1;i<=N;++i) 
    { 
     for(int j=1;j<=N;++j) 
     { 
      if((i+2)<=N && (i+1)<=N && (j-2)>=1 && (i-1)>=1 && (j-1)>=1) 
      dp[i][j]=max((coins[i] + min(dp[i + 2] [j], dp[i + 1][ j - 1])),coins[j] + min(dp[i] [j - 2], dp[i - 1] [j - 1])); 
     } 
    } 
    cout<<dp[1][N]<<endl;//Answer 
} 

return 0; 

}