1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Use dynamic programming.

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.

This is basically an adaptation of the dynamic programming algorithm for the knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem

$\endgroup$
  • $\begingroup$ Eh I totally forgot about the $k$ limit in my answer, oops. $\endgroup$ – orlp May 6 '17 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.