动态规划问题：最大化所有仓位的价值之和

Question

在最近的一次 phone 面试中，有人问我以下动态规划问题，但我想不出一个算法来解决它：

假设有一条路径有 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 个位置），returns 所有位置值的最大总和。它应该以 n.

的多项式函数为界

示例输入：[['A', 'C'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'C'], ['A', 'B', 'C']] 预期输出：13

考虑到我的 phone 面试已经结束，而且我再三思量后仍然无法解决这个问题，我宁愿现在只看到一个可行的解决方案。谢谢！

Answer 1

解题的关键是要认识到，给定一个排列A和某个score，追加一个元素[=20=后A的新分数] 仅取决于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）之后，所有可能的 'last two' 元素以及包含这些 'last two' 元素的任何排列的最高分数：

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]，尽管我们只关心最后两个值和分数。

所有五个子集后，可行的'last two elements'排列和任何对应排列的最大分数为：

[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

所以我们可以return 13. 通过在整个算法中进行额外的簿记，我们还可以重建完整的排列。

这是 three-variable 动态规划 (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))

您问题的答案是任何有效 a 和 b 的最大值 DP(n-1, 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

Answer 2

我比较确定这个迭代版本总是产生最大值，尽管我无法证明这一点。

注意：这假设每个集合不包含重复项，如果是这样则需要稍作修改

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

动态规划问题：最大化所有仓位的价值之和

Dynamic programming problem: maximize the sum of the value of all positions

algorithm

recurrence

memoization

dynamic-programming