Fractional Knapsack Problem

[arush]

Hello,
I would greatly appreciate it if some one could shed some light on
this problem.
The 0/1 Knapsack problem has been proven to be NP complete for a
single knapsack as well as the multiple knapsack cases.
The fractional knapsack (single knapsack case) exhibits greedy optimal
solution.

My questions is as follows:
Does the fractional knapsack (multiple knapsack case) also exhibit the
same greedy solution or is it NP-Hard.
I have two versions of this problem that i am considering:
Case 1: you can use the remaining fraction of an item in another
knapsack
Case 2: you cannot use the remaining fraction of an item in another
knapsack

Could someone direct me if the complexity of this problem is known.

Thanks
AG

[GJ Woeginger]

arush <arush...@gmail.com> wrote:
# Hello,
# I would greatly appreciate it if some one could shed some light on
# this problem.
# The 0/1 Knapsack problem has been proven to be NP complete for a
# single knapsack as well as the multiple knapsack cases.
# The fractional knapsack (single knapsack case) exhibits greedy optimal
# solution.
#
# My questions is as follows:
# Does the fractional knapsack (multiple knapsack case) also exhibit the
# same greedy solution or is it NP-Hard.
# I have two versions of this problem that i am considering:
# Case 1: you can use the remaining fraction of an item in another
# knapsack
# Case 2: you cannot use the remaining fraction of an item in another
# knapsack
#
# Could someone direct me if the complexity of this problem is known.

This looks like homework...

Anyway, Case 1 is polynomially solvable; you should try some LP-formulation.
Case 2 is NP-hard, and this really is just a two-line exercise once you
know the NP-hardness proof for subset-sum or knapsack.

--Gerhard

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/