Nitpick: Just because a problem can be formalized as a zero-one integer optimization problem doesn’t mean it’s NP-complete; you need to show that some NP-complete problem reduces to the planning problem. For example, the problem of finding the largest number in a set {ni} is a zero-one optimization problem (it can be formalized as max∑ixini subject to ∑ixi=1 with each xi being zero or one) but it isn’t NP-complete.
That said, the problem you specified is identical to the knapsack problem, which is known to be NP-complete, so your point stands.
That’s a fair nitpick, thanks. I was aware it was identical to the knapsack problem, though I do see that my phrasing implied that being a zero-one integer optimization problem automatically makes it NP-Complete. That was sloppy of me.
Nitpick: Just because a problem can be formalized as a zero-one integer optimization problem doesn’t mean it’s NP-complete; you need to show that some NP-complete problem reduces to the planning problem. For example, the problem of finding the largest number in a set {ni} is a zero-one optimization problem (it can be formalized as max∑ixini subject to ∑ixi=1 with each xi being zero or one) but it isn’t NP-complete.
That said, the problem you specified is identical to the knapsack problem, which is known to be NP-complete, so your point stands.
That’s a fair nitpick, thanks. I was aware it was identical to the knapsack problem, though I do see that my phrasing implied that being a zero-one integer optimization problem automatically makes it NP-Complete. That was sloppy of me.