So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if the list A is [a,b,c] and the list B is [d,f,g], a valid merge between the two may be [d,a,f,b,g,c], or even just the concatenation of both: [a,b,c,d,f,g], but not [b,c,f,d,c,g,a]. I know I have in total $\binom{|A| + |B|}{|A|}$ ways of merging these lists and maintaining this property, however I have to select one based on the following constraint:

Every pair of exercises $(e_1,e_2)$ has a burnout function $\delta : (e_i,e_j) \mapsto \mathbb{Z}$ associated to them, and I want to obtain a merged list resulting from the lists $r_1 = [e_{11},e_{12},\ldots,e_{1n}]$ and $r_2 = [e_{21},e_{22},\ldots,e_{2n}]$ such that the total sum resulting of adding every pair of elements applied to the function $\delta$ in $r_3$ is minimum, that is to say, that the following sum applied to $r_3$ is the minimum possible.

$$ \sum_{i=0,j=i+1}^{n-1} \delta(r_3[i],r_3[j]) $$

I was able to solve this using a brute force approach, so basically calculating the $\binom{|A| + |B|}{|A|}$ lists that maintain relative order, and then just calculating the total sum in everyone of them and keeping the one with minimum total sum.

An example would be:

$r_1 = [\text{scissor kicks}, \text{scissor kicks}]$

$r_2 = [\text{mountain climbers},\text{mountain climbers}]$

$\delta(\text{scissor kicks}, \text{mountain climbers}) = 4$

$\delta(\text{mountain climbers}, \text{scissor kicks}) = 3$

$\delta(\text{mountain climbers}, \text{mountain climbers}) = 10$

$\delta(\text{scissor kicks}, \text{scissor kicks}) = 10$

In this case, merging these two lists maintaining relative order while at the same time minimizing the total sum would result in $r_3 = [\text{mountain climbers},\text{scissor kicks},\text{mountain climbers},\text{scissor kicks}]$, which has a total sum of 10.

I know this problem can be solved using a dynamic programming approach in polynomial time however I've not been able to think of a solution yet.

  • $\begingroup$ I suggest you follow the advice in cs.stackexchange.com/tags/dynamic-programming/info for how to systematically approach dynamic programming problems and tell us how far you got. Have you found a recursive algorithm (even one that takes exponential time)? $\endgroup$ – D.W. Apr 21 at 5:57
  • $\begingroup$ @D.W. I’d say my main problem so far is not having been able to think of a recursive solution. $\endgroup$ – Jere Apr 21 at 13:07
  • $\begingroup$ If you read through the resources there, they give you a systematic way to try to come up with a recursive solution, by suggesting different subproblems you can try to use. Why don't you show your attempts to construct a recursive algorithm for each of the plausible subproblem definitions suggested by the methods there? $\endgroup$ – D.W. Apr 21 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.