Algorithm for selecting a subset of nodes (K <N) from a chain

Question

I am looking for an algorithm to select a subset of nodes from a chain. For example, with a given node set with "N" nodes in a temporal chain, I would like to select "K" nodes based on the criteria such that K < N. For example, what if I have to select a set of days {D1, D2, DK} with "K=3" days out of the set {D1, D2, D3,...DN} "N=7" days in a week such that I maximize the following cost given by:

I need to select the best "K" items from the set {D1,....,DN}. One possibility is that I can enumerate all possible choices and choose the best combination:

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

...

Is there a well-known algorithm in Computer Science to solve this problem? If so, any pointer to appropriate resources/code might help.

PS: I am not sure whether this is the right forum, please comment below, I will repost it.

Answer 1

Since the objective is linear, this problem has optimal substructure and thus is amenable to dynamic programming. For each i from 0 to K, for each j from 0 to N, determine the best way to choose i nodes from the first j. There's only one way to choose i = 0 nodes. The best way to choose i nodes from the first j > 0 is either the best way to choose i from the first j - 1, or item j preceded by the best way to choose i - 1 nodes from the first j - 1. By avoiding recomputing the optima for subproblems, the running time is polynomial.