瞭解尋找最佳策略的解決方案，包括挑選金壺

我無法理解this question on CareerCup解決方案背後的原因。瞭解尋找最佳策略的解決方案，包括挑選金壺

花盆黃金遊戲：選手A & B.有黃金盆一條線佈置，每個都包含了一些金幣（玩家可以看到多的硬幣是如何出現在每個第一桶金 - 完美信息）。他們得到交替輪次，其中玩家可以從線路的末端之一挑選一個鍋。贏家是最後有更高號碼的玩家。目標是「最大化」A收集的硬幣的數量，假設B也發揮最佳效果。 A開始比賽。

這個想法是找到一個最佳策略，讓A贏得知道 B也玩的最佳。你會怎麼做？

最後我被要求編寫這個策略！

這是Google訪談中的一個問題。

提出的解決方案是：

function max_coin(int *coin, int start, int end): 
    if start > end: 
     return 0 

    // I DON'T UNDERSTAND THESE NEXT TWO LINES 
    int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1)) 
    int b = coin[end] + min(max_coin(coin, start+1,end-1), max_coin(coin, start, end-2)) 

    return max(a,b)

有兩個具體的部分我不明白：

在第一行，爲什麼我們使用範圍[開始+ 2，結束]和[開始+ 1，結束 - 1]？它總是拋出一個硬幣罐。它不應該[開始+ 1，結束]，因爲我們把開始的硬幣罐拿出來了嗎？
在第一行中，爲什麼我們取兩個結果的最小值而不是最大值？
因爲我對兩條線爲什麼會最小以及爲什麼選擇這些特定範圍感到困惑，我不確定a和b究竟代表什麼？

來源

2014-03-05 tina nyaa

你確定這是java嗎？ –

你必須遞歸地解決每個子任務。 – sp1rs

a和b這裏分別代表最大的A可以通過選擇起始罐或結束罐來獲得。

實際上我們試圖最大化A-B，但由於B = TotalGold - A，我們試圖最大化2A - TotalGold，由於TotalGold是不變的，我們試圖最大化2A，這是一樣的A，所以我們完全忽略B的值的選擇，並只與A一起工作。

在遞歸調用更新的參數包括B採摘以及 - 所以coin[start]代表A採摘開始，然後B挑選從一開始下一個，所以它是start+2。對於下一個電話，B從最後選擇，因此它是start+1和end-1。其餘的同樣如此。

我們正在做的min，因爲B會盡量讓它自己的利益，所以它會選擇最小化A的利潤的選擇。

但實際上我認爲這個解決方案缺乏一點意義，它只是返回一個單一的值，而不是「最佳策略」，在我看來，這將是一系列動作。而且它也沒有考慮到A不可能贏的可能性，在這種情況下，人們可能希望輸出一條消息，說這是不可能的，但這真的是要與面試官澄清的事情。

來源

2014-03-05 11:03:47 Dukeling

讓我以相反的順序回答你的觀點，不知何故它似乎更有意義。

3 - a，b表示硬幣的第一個球員將獲得的金額，當他/她選擇的第一或相應的最後一桶

2 - 我們取最小值，因爲這是第二次的選擇玩家 - 他/她將採取行動，儘量減少第一名玩家獲得的硬幣數量

1 - 第一行介紹場景 - 如果第一個玩家拿到第一個玩家，第二個玩家會做什麼？如果他/她再次拿到第一個底池，它將離開（開始+ 2，結束）。如果他/她拿到最後一個罐子，它將離開（開始+1，結束-1）

來源

2014-03-05 11:03:24

首先a和b分別表示start（分別爲end）被播放時的最大增益。

所以我們解釋一下這行：

int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))

如果我打start，我會立即獲得coin[start]。其他玩家現在必須在start+1和end之間玩。他發揮最大的收益。然而，由於硬幣的數量是固定的，這相當於使我的錢最小化。需要注意的是

如果他扮演start+1我會獲得max_coin(coin, start+2, end)
如果他扮演end生病增益max_coin(coin, start+1, end-1)

因爲他試圖儘量減少我的收穫，我將獲得最低的兩個。

同樣的推理適用於我玩的其他線路end。

注意：這是一個不好的遞歸實現。首先計算兩次max_coin(coin, start+1, end-1)。即使你解決了這個問題，你也會在很短的時間內完成計算。這與如果您嘗試使用遞歸計算斐波納契數字的情況非常相似。使用記憶或動態編程會更好。

來源

2014-03-05 11:05:13 hivert

你能解釋一下如何用動態規劃解決上述問題。 –

@coder_15您只需將中間值存儲在表中或類似的地方以避免重新計算它們。 –

加1以獲得更好的解釋 – Humoyun

假設你在你的回合中獲得的是x並且你在所有輪流中得到的結果是y。這兩個值代表x+y，其中a假設您從前面拿下一個底池（x=coin[start]），b假定您從後面拿下您的下一個底池（x=coin[end]）。

現在你如何計算y。

經過您的選擇後，對手將使用相同的最佳策略（因此遞歸調用）來最大化他的利潤，並且您將在本回閤中獲得較少的利潤。這就是爲什麼你的y=min(best_strategy_front(), best_strategy_end()) - 你的價值是剩下的兩個選擇中較小的一個，因爲對手會選擇更大。

索引只是表示您做出選擇後，其餘序列在正面和背面減去一個底部。

來源

2014-03-05 11:08:23

瞭解尋找最佳策略的解決方案，包括挑選金壺

回答

相關問題