Comments on "Which combinatorial problem is similar to this problem?"
You are probably assuming that the cost function is efficiently computable, so that &quot;does there exist a selection of the $n$ options with less than $c$ cost&quot; is an NP decision problem. This assumption is not actually stated in the original question. The question merely states &quot;The cost function can be any function, not necessarily linear.&quot;
As D.W.'s answer says, &quot;you will need to know something about the cost function and take advantage of some structure or properties it has.&quot; Making the assumption that the cost function can be computed in time polynomial in $n$ gives it a little bit of structure. (Exactly how much structure this gives it is the essence of the P vs. NP problem.)