Design, code, and test a C program that uses dynamic programming to determine two separate subsequences of the input such that the first subsequence sums to the first target value and the second subsequence sums to the second target value.

The input should be read from standard input (which will be one of 1. keyboard typing, 2. a shell redirect (<) from a file, or 3. cut-and-paste. Do NOT prompt for a file name!). The first line of the input will give n, the length of the sequence, along with the two target values. Each of the remaining input lines will include one sequence value. All values will be positive integers.

Your program should echo the target values and the input sequence. If a problem instance has a solution, each of the two subsequences should be output and clearly labeled. A message should be provided for instances without a solution. Getting Started: 1. Unlike the one-dimensional situation for ordinary subset sums, this problem is two dimensional. 2. Dynamic programming is the only acceptable method for doing this lab. Do not use a greedy approach! Input file along with sample output

input1.dat 7 9 11 1 2 3 4 4 5 8 output1.dat Targets are 9 and 11 i S ------- 1 1 2 2 3 3 4 4 5 4 6 5 7 8 subsequence for 9: 1 8 subsequence for 11: 3 4 4

input2.dat 6 10 10 3 3 5 5 6 8 output2.dat Targets are 10 and 10 i S ------- 1 3 2 3 3 5 4 5 5 6 6 8 No solution

input3.dat 22 1265 1290 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484

output3.dat Targets are 1265 and 1290 i S ------- 1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64 9 81 10 100 11 121 12 144 13 169 14 196 15 225 16 256 17 289 18 324 19 361 20 400 21 441 22 484 subsequence for 1265: 36 144 324 361 400 subsequence for 1290: 4 9 16 49 64 81 100 121 169 196 225 256