[algogeeks] Re: optimal assignnment of program to tapes.

[Dhyanesh]

Your solution is perfectly right. But this is NP hard problem and O(n L ). So for exponential L, the program runs into exponential time.

-Dhyanesh

On 3/8/06, Karthik Singaram L <[EMAIL PROTECTED]> wrote:

This is the problem of dividing a set into two such that the sum of their differences is minimum.This can be solved using dynamic programming as follows:

algo:

1. Create an array of size L say Arr[L] and initialize to zeroes

2. Put Arr[0]=1

3. For each program Pi

          Scan the array Arr from the right and if Arr[j]=1 then set Arr[j+Li]=1

4. From the right choose the first j such that Arr[j]=1 that will be the Length in S1 and the remaining will be Length in S2

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---