从链中选择节点子集 (K < N) 的算法

Question

我正在寻找一种算法来从链中选择节点的子集。例如，对于时间链中具有“N”个节点的给定节点集，我想根据 K < N 的条件选择“K”个节点。例如，如果我必须选择一组天数怎么办{D1, D2, DK} 在集合 {D1, D2, D3,...DN} 中有“K=3” 天，一周中有“N=7” 天，这样我可以最大化以下给出的成本:

我需要从集合 {D1,....,DN} 中选择最好的“K”项。一种可能是我可以枚举所有可能的选择并选择最佳组合:

...
1 0 0 0 0 1 1
0 0 0 0 1 1 1 
0 1 0 0 1 1 0

...

计算机科学中是否有著名的算法可以解决这个问题？如果是这样，任何指向适当资源/代码的指针都可能有所帮助。

PS:不知道这个论坛对不对，欢迎在下方留言，我会转载

Answer 1

由于目标是线性的，因此该问题具有最优子结构，因此适用于动态规划。对于从 0 到 K 的每个 i，对于从 0 到 N 的每个 j，确定从第一个 中选择 i 节点的最佳方法>j。只有一种方法可以选择 i = 0 个节点。 The best way to choose i nodes from the first j > 0 是从第一个j<中选择i的最佳方式 - 1，或者项目 j 前面选择 i 的最佳方式 - 从第一个 j - 1 开始的节点。通过避免重新计算子问题的最优值，运行时间是多项式的。