Max Knapsack equivalent problem

[JohnDoe2013]

Hi,

I'm working on the decision version of the Knapsack optimization problem that asks whether there is a subset of the items with a total value of at least V and where the total weight of the items is at most W.

I'm looking for an equivalent problem P for this version of the knapsack problem. This means that:

1) P is reducible to Knapsack
2) Knapsack is reducible to P

I have tried PARTITION and SUBSET-SUM but I'm only able to reduce them to Knapsack. I have not been able to find a reduction from Knapsack to either of them.

Am I using the wrong problems? If so, what would be a more suitable equivalent problem?

Thanks.

 

[lofgran]

Hi there,

I would recommend looking into the 0-1 Integer Linear Programming (ILP) problem as an equivalent problem for the decision version of the Knapsack optimization problem. ILP involves finding a solution to a linear system of equations with the additional constraint that all variables must take on integer values of either 0 or 1.

To show that ILP is reducible to Knapsack, you can use the same approach as the reduction from PARTITION or SUBSET-SUM. The key is to represent the ILP problem as an instance of Knapsack, where the weight of each item corresponds to the coefficient of the variable in the linear system and the value of each item corresponds to the constant term in the linear system. This way, a solution to the Knapsack problem will also provide a solution to the ILP problem.

Similarly, to show that Knapsack is reducible to ILP, you can represent the Knapsack problem as an instance of ILP by setting up a linear system of equations with the weight and value constraints.

I hope this helps and good luck with your research!