# Need to show the equivalence of the two combinatorial optimisation problems

I have the following problem. Given a graph $G=(V,E)$ with node costs, the task is to select a subset of nodes $S$ such that its cost $h(S)$, which is sum of costs of all nodes in S, does not exceed a given parameter $C$ and $|S|$ is maximised. I can express this problem as follows: $$\max. f=|S|\quad\text{ such that }\quad h(S) \leq C$$ Basically, I want to select as many nodes as possible without exceeding $C$. If I'll choose the nodes with smallest costs, this will maximise the number of nodes in $S$. I want to formally show the equivalence between these two problem: $$\max. \{f\; |\; h(S) \leq C\} \Longrightarrow \min. \{h(S)\}\quad\text{ and }\quad h(S) \leq C$$ I would really appreciate any suggestions or links/references.

-
Why is this problem stated in terms of graphs? It doesn't involve adjacencies or edges at all. Also, the problem on the right makes no sense: the minimum value of $h(S)$ is clearly $0$. The dual problem is more like "minimize $h(S)$ subject to a lower bound on $|S|$". –  Erick Wong Jul 15 '12 at 6:07
Thanks for your answer. I have simplified the cost function that involved edge costs as well. You are right, the dual problem should be constrained. Is there a way to show the equivalence between this problem and its dual, i.e., go from max to min? –  vn1k Jul 16 '12 at 2:16