No. The 15th processor starts with those 4 items already in the knapsack. This makes it a smaller problem because you don't have to consider cases where those 4 items are not in the knapsack. Similarly, processor 0 starts with none of those 4 items in the knapsack and does not consider any combinations including any of those 4 items. Essentially you are removing those 4 items from the problem. Don
On Apr 1, 3:00 am, bharat b <[email protected]> wrote: > @don : still i didn't understand the logic .. 15th processor has to find > the best possible case which includes all 4 items along with 36 items..is > it not same as 40 items 0-1 knapsack? > > On Wed, Mar 28, 2012 at 8:54 PM, Arun Vishwanathan > <[email protected]>wrote: > > > > > > > Thanks Don! > > > On Wed, Mar 28, 2012 at 7:09 AM, Don <[email protected]> wrote: > > >> Let's say that you have 16 processors. You are trying to solve the 0-1 > >> knapsack problem for 40 items. > >> Each item i has size S[i], and you need to find the subset of items > >> which sums as close to T as possible without exceeding T. > > >> Pick four of items. There are 16 possible combinations of those items: > >> 0000 (none of those 4 items included) > >> 0001 (only item #1 included) > >> ... > >> 1111 (all four items included) > > >> You will essentially ask each of the 16 processors to solve the > >> knapsack problem for 36 items, starting with one of the 16 possible > >> combiations of the 4 items. Processor 0 will start with none of the > >> first 4 items. Processor 15 will start with all of them, and the other > >> processors will start with a different subset of the items. It may > >> seem like solving the problem for 36 items is not much different than > >> 40, but it requires 1/16th of the work. When each processor is done, > >> it knows the best solution including its assigned items from among the > >> first 4 items. To find the overall best solution you just need to > >> compare the 16 solutions and pick the one best. > > >> A possible improvement is to divide up the problem into more parts and > >> farm them out to the processors as they become available. This would > >> work better if you don't have a power of 2 number of processors. It > >> also would reduce the tendancy for some processors to finish early and > >> sit idle while one or two take longer to finish their portion of the > >> work. > > >> Don > > >> On Mar 28, 9:51 am, Arun Vishwanathan <[email protected]> wrote: > >> > @Don: I am not clear with your explanation. Please can you give me an > >> > example? > > >> > On Wed, Mar 28, 2012 at 6:19 AM, Don <[email protected]> wrote: > >> > > If you have n processors, start with the n possible ways to select > >> > > from log2 n items. Assign each processor to find a solution based on > >> > > the resulting subset of remaining items. Each processor should be able > >> > > to work fairly independently, and when they are done, they can compare > >> > > results and find the best one. > >> > > Don > > >> > > On Mar 27, 10:47 pm, Arun Vishwanathan <[email protected]> > >> wrote: > >> > > > Hi all, > > >> > > > I am planning to implement a parallel version of the 0-1 knapsack > >> > > problem. > >> > > > I tried reading up a bit and there are few suggestions here and > >> there. > >> > > > However I would like to know if anyone has an idea or links that I > >> cud > >> > > > refer for this? The main problem in parallelizing a DP algorithm is > >> the > >> > > > dependencies due to recursion? Is there an effective strategy for > >> this?? > >> > > > Using shared memory or message passing approach? > > >> > > > Arun > > >> > > -- > >> > > You received this message because you are subscribed to the Google > >> Groups > >> > > "Algorithm Geeks" group. > >> > > To post to this group, send email to [email protected]. > >> > > To unsubscribe from this group, send email to > >> > > [email protected]. > >> > > For more options, visit this group at > >> > >http://groups.google.com/group/algogeeks?hl=en. > > >> > -- > >> > "People often say that motivation doesn't last. Well, neither does > >> bathing > >> > - that's why we recommend it daily."- Hide quoted text - > > >> > - Show quoted text - > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to [email protected]. > >> To unsubscribe from this group, send email to > >> [email protected]. > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > "People often say that motivation doesn't last. Well, neither does > > bathing - that's why we recommend it daily." > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > > **Regards > * > * <[email protected]> > > Bharat B | M.Tech II | C.S.E | IITM > * > * > *Ph: +91 8056127652*- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
