Description
For the following problem, write the general form that enables you to use the Dynamic Programming strategy to
find the optimal solution. Implement the designed approach, and then add some test cases and draw the produced
table from your program (you may need to write a piece of code to generate some large test cases).
Max LED Lighting
Suppose that you were given two circuit boards (S and L), where S contains n power sources, while L contains n
LEDs. The sources on S are sorted in ascending order <1, 2, 3, … , n>, while the LEDs on L are not <2, 9, 5, 14, 3,
…>. You were asked to connect each LED in L to its pair in S (i.e., 1 with 1, 2 with 2) through unshielded wires,
thus when a wire connects a LED (li) in L with its corresponding source in S (si), it may prevent other LEDs from
being connected (no two wires may cross).
In the below example, if you connected l1 with s1, then only one LED will be lighted.
2
6
3
5
4
1
1
2
3
4
5
6
While if you connected {l2 , s2}, {l3 , s3}, and {l4 , s4}, then 3 LEDs will be lighted as shown in the figure
below.
2
6
3
5
4
1
1
2
3
4
5
6
Your job is to find the best pairs to be connected, so the maximum number of LEDs are lighted.
The input of your program must be: n (number of LEDs, say 100) and a permutation of numbers (<1 to n>)
that represent the ordering of the LEDs on the board L. The output of the program must be the maximum
number of LEDs that you can light, and what are they. An example input file is below:
6
2 6 3 5 4 1