2
$\begingroup$

Given two unbounded knapsack instances, $K_1 = (W_1, weights, values), K_2 = (W_2, weights, values)$, where $W_1 \ne W_2$, what is the complexity of determining $v(K_1) = v(K_2)$ where $v$ returns the optimal sum of values given a knapsack instance?

I know that the decision problem of knapsack -- i.e. asking whether or not a knapsack instance can achieve a value of at least $k$ is NP-hard, but am having trouble reducing that to this particular decision problem. I conjecture that this remains NP-hard though.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

I have no proof, but I expect it's probably hard, because given a target value $t$, it is easy to construct a knapsack problem $K_2$ whose optimal value is $t$. This means that your problem is at least as hard as testing, given $t$ and $K_1$ whether the optimal value of $K_1$ is equal to $t$. I don't know whether that problem is NP-hard, but the related problem of testing whether the optimal value of $K_1$ is $\ge t$ is NP-hard.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.