Prev: The real deal: Proof of Cook's Theorem in Unary - Thank you Sci.Math for your patience and kindness
Next: Fractional Knapsack Problem
From: arush on 13 Nov 2009 19:38
Hello All.
I was wondering if someone could shed some light on this topic.

The one dimensional Knapsack problem (0/1) knapsack is a NP complete
problem.
The fractional version of this problem ( where in you can take a
fraction of the item ) is shown to optimal in polynomial time.

I have a problem where in i have multiple knapsacks and i can take a
fraction of an item and place it in the knapsack. However i am not
allowed to use the remaining fraction of that item in any other
knapsack. Is this problem NP - Complete or can be solved in polynomial
time.

Thank you for your time,
AG
 | 
Pages: 1
Prev: The real deal: Proof of Cook's Theorem in Unary - Thank you Sci.Math for your patience and kindness
Next: Fractional Knapsack Problem