New answers tagged

1

You can't, not efficiently (unless P=NP). Suppose there was a polynomial-time algorithm $A$ to check whether a given solution is optimal. Then there would be a polynomial-time algorithm to solve the knapsack decision problem, i.e., given a problem instance and a value $V$, check whether there exists any solution with value $>V$. Here is how: you add a ...


Top 50 recent answers are included