StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PODynamic programming recurrence relation
text
Body
copied!<p>I am trying to find and solve the recurrence relation for a dynamic programming approach to <a href="http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2445" rel="nofollow">UVA #11450</a>. As a disclaimer, this is part of a homework assignment that I have mostly finished but am confused about the analysis.</p> <p>Here is my (working) code:</p> <pre><code>int shop(int m, int c, int items[][21], int sol[][20]) { if (m < 0) return NONE; // No money left if (c == 0) return 0; // No garments left if (sol[m][c] != NONE) return sol[m][c]; // We've been here before // For each model of the current garment for (int i = 1; i <= items[c-1][0]; i++) { // Save the result int result = shop(m-items[c-1][i], c-1, items, sol); // If there was a valid result, record it for next time if (result != NONE) sol[m][c] = max(sol[m][c], result+items[c-1][i]); } return sol[m][c]; } </code></pre> <p>I am having trouble with a few aspects of the analysis:</p> <ul> <li>What is the basic operation? My initial reaction would be subtraction, since each time we call the function we subtract one from C.</li> <li>Since the recursive call is within a loop, does that just mean multiplication in the recurrence relation?</li> <li>How do I factor in the fact that it uses a dynamic table into the recurrence relation? I know that some problems decompose into linear when a tabula is used, but I'm not sure how this one decomposes.</li> </ul> <p>I know that the complexity (according to <a href="http://www.algorithmist.com/index.php/UVa_11450" rel="nofollow">Algorithmist</a>) is O(M*C*max(K)) where K is the number of models of each garment, but I'm struggling to work backwards to get the recurrence relation. Here's my guess:</p> <p>S(c) = k * S(c-1) + 1, S(0) = 0</p> <p>However, this fails to take M into account.</p> <p>Thoughts?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload