# Tag Info

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 ...