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
@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
aaron.nar...@gmail.comwrote:
Thanks Don!
On Wed, Mar 28,
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
@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 dondod...@gmail.com 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
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
Thanks Don!
On Wed, Mar 28, 2012 at 7:09 AM, Don dondod...@gmail.com 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