MHB Max Knapsack equivalent problem

  • Thread starter Thread starter JohnDoe2013
  • Start date Start date
  • Tags Tags
    Equivalent Max
AI Thread Summary
The discussion centers on finding an equivalent problem P for the decision version of the Knapsack optimization problem, which seeks a subset of items with a total value of at least V and a total weight not exceeding W. The original poster has attempted to use PARTITION and SUBSET-SUM but could only reduce them to Knapsack, not vice versa. A recommendation is made to consider the 0-1 Integer Linear Programming (ILP) problem as a suitable equivalent. The ILP problem can be reduced to Knapsack by representing its linear equations with item weights and values. Conversely, Knapsack can also be represented as an ILP problem, demonstrating the reducibility in both directions. This approach offers a promising avenue for further exploration in the context of the Knapsack problem.
JohnDoe2013
Messages
3
Reaction score
0
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.
 
Technology news on Phys.org


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!
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Back
Top