找到最佳相邻对,以便最大化第一个元素的总和

Question

我在接受采访时被问到这个问题,但无法弄明白并希望知道答案.

假设我们有一个这样的列表:

1 7 8 6 1 1 5 0

我需要找到一个算法,使它与相邻的数字配对.目标是最大化利益,但只计算对中的第一个数字.

例如,在上面,最佳解决方案是:

{7,8} {6,1} {5,0}

所以当只采取第一个:

7 + 6 + 5 = 18.

我尝试了各种贪婪的解决方案,但他们经常选择{8,6}导致非最佳解决方案.

思考？

Answer 1

首先,观察跳过多个数字^*是没有意义的.然后,观察通过比较两个数字可以构建这个问题的答案:

• 你跳过第一个数字的子问题的答案,和
• 保留第一个数字的子问题的答案

最后,观察到只有一个数字序列的问题的答案是零,并且只有两个数字的问题的解决方案是两个数字的第一个数字.

掌握了这些信息后,您可以构建一个针对该问题的递归memoized解决方案,或者从后面开始的动态编程解决方案,并返回决定是否包含先前的数字.

^*证明:假设您有一个产生最大总和的序列,并且它跳过原始序列中的两个数字.然后,您可以添加您跳过的对,并改进答案.

Answer 2

一个简单的动态规划问题。从一个特定索引开始，我们可以在 当前索引处生成一对，或者跳到下一个索引：

int []dp;//Array to store result of sub-problem
boolean[]check;//Check for already solve sub-problem

public int solve(int index, int []data){
    if(index + 1 >= data.length){//Special case,which cannot create any pair
        return 0;
    }
    if(check[index]){//If this sub-problem is solved before, return the value
        return dp[index];
    }
    check[index] = true;
    //Either make a pair at this index, or skip to next index
    int result = max(data[index] + solve(index + 2, data) , solve(index + 1,data));
    return dp[index] = result;
}