1
$\begingroup$

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

$\endgroup$

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.