A dynamic programming problem - in feud with the faculty

Discussion in 'Software' started by mynameisfingers, Mar 21, 2007.

  1. mynameisfingers

    mynameisfingers Private E-2

    Here is a dynamic programming problem and my proposed solution. I came up with an O(n2B) algorithm, but is that the best that is possible? Also, are there any problems with my solution?

    Full solution and implemented C++ code can be found here:
    http://www.geocities.com/krayzieway2000/ItemsAndBound.html

    Given n items of size l1, …, ln (positive integers) and a bound B (non-negative integer), develop a dynamic programming algorithm (pseudocode and explanation) that determines whether there exists a subset S {1, …, n} of the items such that their total size equals B, ie. Σli = B (sum over i є S). Argue on the correctness of your algorithm and explain its runtime.

    Answer:

    Let M[i,j] = 1 if we can use items 1..i to get Σli = j, 0 otherwise.

    Then M[i,j] = max{M[k-1,j - lk] for k = 1..i, lk ≤ j, M[i - 1,j] if li > j}

    Proof/Explanation:
    If we have an integer lk, we would like to know if we can form the sum j using items l1..lk.
    If we can form the sum j-lk using items l1..lk-1, then we can form the sum j using l1..lk because j - lk + lk = j.
    Max{ } ensures we get a 1 if we can form the sum.
    The answer is in M[n,B] (ie. if M[n,B] = 1  return true).
    We can use backpointers M[n,B].Previous() to determine which items were used but this is not part of the pseudocode for simplicity.

    Pseudocode:
    Assume M[0,j] = 0, all M[i,j] initialized to 0

    for (j = 0..B)
    {
    for (i = 1..n)
    {
    for (k = 1..i)
    {
    if (lk ≤ j) & (M[k-1,j-lk] > M[i,j])
    then M[i,j] = 1
    }
    }
    }

    Runtime:
    Outer: O(B)
    Inner O(1 + 2 + 3 + … + n) = O(n2) -> Total O(n2B)
     

MajorGeeks.Com Menu

Downloads All In One Tweaks \ Android \ Anti-Malware \ Anti-Virus \ Appearance \ Backup \ Browsers \ CD\DVD\Blu-Ray \ Covert Ops \ Drive Utilities \ Drivers \ Graphics \ Internet Tools \ Multimedia \ Networking \ Office Tools \ PC Games \ System Tools \ Mac/Apple/Ipad Downloads

Other News: Top Downloads \ News (Tech) \ Off Base (Other Websites News) \ Way Off Base (Offbeat Stories and Pics)

Social: Facebook \ YouTube \ Twitter \ Tumblr \ Pintrest \ RSS Feeds