非连续元素的最大总和（来自任何地方的k个元素）

Question

“给定一个正整数数组的问题的改进版本，从这个数组中找到非连续元素的最有效算法是什么，当它们加在一起时，产生最大总和？”标准版本得到了很好的回答here。

但是，如果您也可以从列表中的任何位置选择指定数量的元素，无论它们是否连续，该怎么办？在这种情况下，您如何找到最大金额？

举一个例子，说你正在建房子。你有n个房屋可供选择。每个地段都有与之相关的财务价值，如果你在那里建房子，你会得到X [i]。但是，由于分区法则，你不能在连续批次上建立（所以如果你建立在第5批，你不能建立在＃4或＃6上）。您希望以最大化价值的方式建造房屋。因此，如果H []是您要建造的房屋清单，问题将是H[i] = max ((H(i-1), H(i-2) + X[i])).

但是现在，如果你有额外的k-zoning许可证（给你k的话）除了固定批次之外你还可以在任何地方建造什么？

Answer 1

这可以通过简单的动态编程算法来解决：

1. 创建一个元组列表（例如tuples）;这个清单包含两个对象：建造房屋的总价值，以及所选房屋清单（例如lots）
2. 将列表初始化为一个元素，值为0，空的批次列表
3. 遍历所有可能的住房地段。为每一批L：
4. 循环遍历列表：对于列表中的每个元组T：
5. 如果房屋可以添加到住宅地块列表中（即列表中少于k个地块，并且添加L不会破坏非连续规则），则在列表中创建另一个元素，将该值合计为T具有建立在这个地段的价值（你称之为X[i]）并将L添加到lots的T列表中。
6. 循环通过tuples，找到一个最大的value。住房地段的最佳选择存储在tuple的lots

不确定这个的复杂性（n ^ 2 * k？ - 现在无法思考）但总体来说并不太糟糕。

关于这一点的好处是：通过一些聪明的编码，您可以将算法重用于任何规则集。只需使第5步接受外部条件。

Answer 2

首先选择k个最佳元素，然后在没有先前选择的元素的情况下解决实例中的“最佳非连续整数”问题。

Answer 3

d[i][j] - 动态，如果第一个未使用的房子是i我们可以采取多少，我们已经使用了j奖金。

d[0][0] = 0;  
d[i][j] = max(d[i-1][j], d[i-2][j] + x[i], d[i-1][j-1] + x[i]);