在最近的一次電話采訪中，我被問到以下動態編程問題，但無法為它提出演算法：
假設有一條帶n 位置的路徑。考慮集合S = {A,B,C}。路徑上的每個位置都有一個關聯的非空子集S。對于路徑上的每個位置，我們可以從其相關子集中選擇一個元素。對于路徑上的給定位置i ，其“值”由與其可以訪問的位置的不同元素的總數決定。它可以訪問的位置由集合給出{i-1, i, i 1} （因為i=1 它是公正{0,1}的，因為i=n 它是公正的{n, n-1}）。我們希望最大化所有倉位的“價值”之和。
因此，例如，如果我有n=5 每個位置的以下子集1…5：
S1 = {A,C}, S2={A, B}, S3={A,B,C}, S4={A,C}, S5={A,B,C}
那么使總和最大化的一種可能的安排是[A, B, C, A, B]，這將是2 3 3 3 2 = 13。
我想撰寫一個演算法，給定一個子集串列（其中第 n 個子集對應于第 n 個位置），回傳所有位置值的最大總和。它應該以 的多項式函式為界n。
示例輸入：[['A', 'C'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'C'], ['A', 'B', 'C']]
預期輸出：13
鑒于我的電話面試已經結束，而且經過深思熟慮后我仍然無法解決這個問題，我寧愿在這一點上看到一個可行的解決方案。謝謝！
uj5u.com熱心網友回復：
解決問題的關鍵是要認識到，給定一個A有一定的排列，附加一個元素后的score新分數只取決于最后兩個元素。Az A
給定一個以（不一定是不同的）元素x和結尾的陣列y，附加一個元素后的分數增加z為：
1 // from z on itself
1 if (z != y and z != x) else 0 // from y gaining z as neighbor
1 if (z != y) else 0 // from z gaining y as neighbor
對于您的示例，前兩個位置有 4 種可能的安排：
Subsets:
S1 = {A, C}, S2 = {A, B},
S3 = {A, B, C}, S4 = {A, C}, S5 = {A, B, C}
After placing the first two elements:
[A, A] max score = 2
[A, B] max score = 4
[C, A] max score = 4
[C, B] max score = 4
在附加第三個元素（來自S3）之后，所有可能的“最后兩個”元素以及與這些“最后兩個”元素的任何排列的最大分數：
After S3 = {A, B, C}
[A, A] max score = 5
[A, B] max score = 7
[A, C] max score = 6
[B, A] max score = 7
[B, B] max score = 5
[B, C] max score = 7
例如，這里唯一的以 結尾的最大分數排列A, A是[C, A, A]，盡管我們只關心最后兩個值和分數。
在所有五個子集之后，排列的可行“最后兩個元素”和任何相應排列的最大分數將是：
[A, A] max score = 11
[A, B] max score = 13
[A, C] max score = 12
[C, A] max score = 13
[C, B] max score = 13
[C, C] max score = 11
所以我們可以回傳 13。通過在整個演算法中進行額外的記賬，我們還可以重建完整的排列。
這是三變數動態規劃（DP）公式：
DP(index, y, z) is defined as the
maximum score for an arrangement on PathArray[0, 1, ..., index]
with final two elements [y, z], for any y in Subsets[index-1]
and z in Subsets[index]
DP(index, y, z) = max over all x in Subsets[index-2] of
(DP(index-1, x, y) AddedScore(x, y, z))
DP(n-1, a, b)您的問題的答案是任何有效a和的最大值b。
當路徑有長度時，我已經排除了基本情況2：您應該直接求解一元和二元情況的分數。
- 有一個元素：分數總是
1。 - 有兩個元素：
4如果元素不相等則得分，否則得分2。
一個 Python 實作：
def dp_solve(subsets):
if len(subsets) == 1:
return 1
def added_value(grandparent, parent, child) -> int:
return (1
(1 if child != grandparent and child != parent else 0)
(1 if child != parent else 0))
pair_dict = collections.Counter()
for x, y in itertools.product(subsets[0], subsets[1]):
pair_dict[x, y] = 4 if x != y else 2
for subset in subsets[2:]:
new_dict = collections.Counter()
for old_key, old_value in pair_dict.items():
grandparent, parent = old_key
for child in subset:
new_value = old_value added_value(grandparent,
parent,
child)
new_dict[parent, child] = max(new_dict[parent, child],
new_value)
pair_dict = new_dict
return max(pair_dict.values())
my_lists = [['A', 'C'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'C'], ['A', 'B', 'C']]
print(dp_solve(my_lists)) # Prints 13
uj5u.com熱心網友回復：
我相對確定這個迭代版本總是產生最大值，盡管我無法證明這一點。
注意：這假設每個集合不包含重復項，如果是這種情況需要稍作修改
if only one position in path, select any value from it's set
else:
starting from first position on path
While (not at last element of path) {
if position set only has 1 value, select it
else if position set has unique value not in neighbors' sets (or single neighbor for ends), select it
else select value that's not the same as prior position, prioritizing a value that's in (next position 1)'s set (assuming that position isn't out of bounds)
outputArray[position] = value
position
}
//at last position
if only 1 value select it
else select a value different from previous
outputArray[position] = value
outputArray should now contain values from each set that maximize distinctness among neighbors
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446411.html
下一篇：這個問題對應于哪個背包問題變體？