Re: Reducing the Knapsack Problem to the Bin Packing Problem
- From: eKo1 <berndlosert@xxxxxxxxxxxx>
- Date: 20 Apr 2007 14:20:10 -0700
Reducing the Bin Packing problem to the Knapsack problem seems to be
much easier. I would implement g(A, B, $) using f as follows:
Let W equal the sum of $(x), x in A. If f(A, $, $, B, W) = 1, then it
is possible to pack all the objects in A into the knapsack of size B
since the total worth of the items in the knapsack is W and W is the
sum of the sizes of the objects in A. This is equivalent to saying
that one can pack the objects in A into B bins.
Am I right?
.
- References:
- Prev by Date: Re: Reducing the Knapsack Problem to the Bin Packing Problem
- Next by Date: hi.....need help in proving this plz.....
- Previous by thread: Re: Reducing the Knapsack Problem to the Bin Packing Problem
- Next by thread: Re: Intractability Problem (reduction form 3SAT)
- Index(es):
Relevant Pages
|
