Reducing the Knapsack Problem to the Bin Packing Problem
- From: eKo1 <berndlosert@xxxxxxxxxxxx>
- Date: 18 Apr 2007 15:32:17 -0700
I just want to confirm my understanding of reducing one problem to
another. In this case, I want to reduce the Knapsack problem to the
Bin Packing problem. Here is the way I would do it.
Let O be the set of objects. If o is in O, then s(o) is its size and
w(o) is its worth. Let K be the size of the knapsack and W the minimum
desired worth. Let f(O, s, w, K, W) be a function that outputs 1 if
there is a subset of O that will fit into the knapsack and have a
total worth of at least W and 0 otherwise.
Now, define a function g(A, B, $) that outputs 1 if there is a way of
packing the set of objects A into B bins and 0 otherwise. Each bin has
a size of 1 and each object a in A has a size $(a) less than or equal
to 1.
Now, I was thinking of implementing f using g as follows:
Let s'(o) = s(o) / K and w'(o) = w(o) / W, o in O.
for each subset O' of O do
// Check if objects O' fit in the knapsack.
if g(O', 1, s') = 1 then
// Check if the objects O' have a worth is greater than W.
if g(O', 1, w') = 0 then
return 1
done
return 0
Hmm...the only problem I see is that I can't check if the worth of the
O' objects is exactly W using g. I could modify g so that it outputs
-1 if there is at least one bin that is not completely filled, 1 if
all the bins are completely filled and 0 otherwise.
What do you think?
.
- Follow-Ups:
- Prev by Date: Re: Dynamic cycle Detection
- Next by Date: Re: How to prove "Cfls are not closed under shuffling"
- Previous by thread: Dynamic cycle Detection
- Next by thread: Re: Reducing the Knapsack Problem to the Bin Packing Problem
- Index(es):
Relevant Pages
|
