# Select largest subset, subject to a separate weighting constraint

Given an unsorted set of tuples $(c, w)$ and a threshold value $W$, I want to select $k$ tuples such that: $$maximize\sum_{i=1}^k c_i \\ \sum_{i=1}^k w_i \ge W$$ It seems pretty simple at first. Without the weighting constraint, you can use any selection algorithm to select the $k$ elements with largest $c$. But with the weighting, it seems there's no special structure to exploit. Seems like you'd have to search all subsets?

Let the $(c,w)$ pairs be $(c_1,w_1),\dots,(c_n,w_n)$. Define $A[k^*,n^*,W^*]$ to be the largest possible sum of $c$-values obtainable by selecting $k^*$ pairs from $(c_1,w_1),\dots,(c_{n^*},w_{n^*})$ such that the sum of their $w$-values is at least $W^*$. Then you can write down a recursive definition of $A[k^*,n^*,W^*]$:
$$A[k^*,n^*,W^*] = \max(A[k^*,n^*-1,W^*], A[k^*-1,n^*-1,W^*-w_{n^*}]+c_{n^*}).$$
Now fill in this table using dynamic programming. The running time will be $O(nkW)$, where $n$ is the number of $(c,w)$-pairs in the input.
• Eh I totally forgot about the $k$ limit in my answer, oops. – orlp May 6 '17 at 10:43