3
$\begingroup$

I am interested in the following variant of the subset sum problem:

Given a set of positive integer weights $w_1,..., w_n$, such that each $w_i$ is polynomial in $n$, and given integers $s$ and $k$, count the number of subsets of weights of cardinality exactly $s$ such that the sum of the weights in each subset is at most $k$.

I expect that there is a polynomial-time dynamic programming algorithm for this problem but don't have a reference. Can anyone please point me to the relevant reference?

$\endgroup$
  • $\begingroup$ Yes. But let us assume that $s$ is not constant. $\endgroup$ – h.a Jul 9 '12 at 18:18
3
$\begingroup$

Even if $s$ is not constant, a dynamic programming algorithm similar to that for the knapsack problem would work. For this to be polynomial time, we need each $w_i$ to be polynomial in $n$ (implying that $k \leq \sum w_i$ is polynomial in n).

The idea is that $T(j,i)$ is the number of subsets of weight $j$ and cardinality $i$. Start with all $T(j,i) = 0$ except $T(0,0) = 1$

Then:

For i = 1 to $n$
For j = 0 to $k$
For h = 1 to $s$
T(w_i + j,h+1) += T(j,h)

Then your answer is $\sum_{j \leq k} T(j,s)$

$s$, $n$, and $w_i$ (and therefore $k$) are all polynomial so all of this is polynomial. Specifically this is at worst $O(n^2k)$ time.

$\endgroup$
  • $\begingroup$ Something seems wrong here in the solution. Consider w_1=1 and w_2=2, then T(2,2)=1. $\endgroup$ – h.a Aug 7 '12 at 22:55

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.