That’s true if you want an optimal solution. If you just want a decent solution (for various definitions of decent), the complexity may not be too bad.