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.
Algorithm for selecting a subset of nodes (K <N) from a chain
Vra
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.
Oplossing