I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset $S$ as $c(S)=\max_{e\in S} w_e$, and we let the set of valid subsets $\mathcal{S}$ to be all $S$ such that $|S| + c(S) \leq d$, where $d$ is a given "capacity" parameter.
I believe that the obvious greedy algorithm -- sort all elements in decreasing order of $w_e$ and construct each set by accumulating them in that order -- is optimal for the problem, but am struggling with moving forward. Can anyone recommend a good way to start?
