I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness.

The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from left to right and not necessarily following the value $v_i$ (meaning the sort order is implicit),(assume those values are the "volumes" of "objects"). The problem also recieve a value $V$ that stands for the maximum volume of both knapsack (there are two knapsack with same supported volume). Each element have volume $v_1, v_2, ..., v_3$ and every one has the same weight (let's say 1). There is a the restriction that If I were to select the item $v_i$ I HAVE to have taken every object from $v_1$ to $v_{k-1}$. Another restriction is that each knapsack must have the same numbers of items.

So I need to take the greatest ammount of objects in the knapsack that the sum of their volume do not exceed the knapsack $V$, and both knapsack must have the same number of objects. ($|knapsack_1| = |knapsack_2|$) And also following the restriction for taking objects.

After trying to reduce from some NP-Complete problems I reduce it from knapsack, but somehow I made a mistake and now I don't know how to do it correctly.

I'll show you what I did:

I used the decision problem for the Knapsack Problem, it recieve a list of tuples $x_i = <p_i, w_i>$ ($p_i$ is the profits of taken element $i$, and $w_i$ is how much object $i$ weights), a value $W$ (for supported weight), and a minimum profits from elements $C$. The problem returns a True if there is a list of $x_i$ ($x_1, x_2, ..., x_n$) that satisfy that $\sum_{i=0}^{n}p_ix_i \geq C$ and $\sum_{i=0}^{n}w_ix_i \leq W$. False otherwise.

After working a little bit with the values, I tried to transform the input from Knapsack problem to my problem. (The one described above). So I tried to find a relation between the Profit and The weight to some how sort the objects following that relation. So I did:

$-\sum_{i=0}^{n}p_ix_i \leq -C$

$\sum_{i=0}^{n}w_ix_i \leq W$

And sum both sums:

$\sum_{i=0}^{n}x_i (w_i - p_i) \leq W - C$

After doing that used the $W-C$ elements as the $V$ for my two knapsack problem, and I sorted the list of elements by their $(w_i - p_i)$. My interpretation was to found a relation between the profit and the weight, and some how guarantee the same result. Then I duplicated every element on the list, for my problem to distribute both objects of the same type if it select them. For example, the list should look like this: $o{_1}{_1}, o{_1}{_2}, o{_2}{_1}, o{_2}{_2}, ..., o{_n}{_1}, o{_n}{_2}$

But problem arises when profit and weight has values very distanct and will get negative numbers and don´t know to work with them properly.

So I´m stuck with this reduction, can any one tell me if I am using the correct aproach, and send me a link, and if not, help me with this!

Thanks in advance


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.