Search code examples
algorithmknapsack-problemproofnp-completeproof-of-correctness

Reducing knapsack problem to an inverse knapsack problem

1)Suppose we have a common 0-1 knapsack problem. Given a set of n items numbered from 1 up to n, each with a weight w_i and a value v_i, along with a maximum weight capacity W. Here we need to select some of the objects, so that maximize sum of v_i, such that sum of w_i of selected objects will not exceed the given W number.

       maximize∑(v_i*x_i), such that ∑(w_i*x_i)≤ W

2)Now suppose we have just the same problem, but we need to select objects so that sum of their values will be minimal, and sum of their weights can't be less than the given number.

      minimize∑(v_i*x_i), such that ∑(w_i*x_i)≥ W.

Knowing that first problem is NP complete, how can I prove that second one has the same complexity, in other words is NP complete too?

Solution

  • Knowing that first problem is NP complete, how can I prove that second one has the same complexity, in other words is NP complete too?

    If you want to prove that problem B is NP-complete, you have to prove that there exists a polynomial time reduction from A to B, where A is known to be a NP-complete problem.
    A polynomial-time reduction from a problem A to a problem B is an algorithm that solves problem A using a polynomial number of calls to a subroutine for problem B, and polynomial time outside of those subroutine calls.(source).

    So in your case, your can easily make a polynomial time reduction from the knapsack problem to the inversed knapsack problem.
    These two problems are equivalent (finding an optimal solution to one immediately solves the other).
    Let S be the set of objects, M be the sum of the weights of the objects of S, and W the capacity of the knapsack. Then, we have:

    • (i) finding a subset of objects such that the sum of their weight does not exceed W and the sum of their value is maximal

    is equivalent to

    • (ii) finding a subset of objects such that the sum of their weight is of at least M-W and the sum of their value is minimal.

    That is because if S' is an optimal solution of (i), then S\S' is an optimal solution of (ii) (and vice-versa).

    This is a polynomial time reduction (O(1) calls to the subroutine, polynomial number of operations), so the inversed knapsack is indeed NP-complete.