Fractional Knapsack Problem
in [Theory]
|
From: arush on 16 Nov 2009 08:33 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
From: GJ Woeginger on 16 Nov 2009 09:12 arush <arushgadkar(a)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/
|
Pages: 1 Prev: Complexity of Knapsack Next: Coins on chess-board puzzle |