Is it easier to solve this version of a problem with a subset?

Question

I have a problem related to the problem of the sum of the subsets , and I wonder if the differences make it easier, that is, resolved in a reasonable amount of time.

Given the value of V, the size of the set L, and the sequence of numbers [1, N] S, how many subsets L of size S are less than V?

This differs from the problem of the sum of the subset in three ways:

• I don't like how many subsets are less than a given value, not how many are equal .
• The sizes of the subset are fixed.
• I don’t care how much sets the amount less than V, and not just whether they exist.

Is there a reasonably efficient algorithm to solve this problem?

Edit: Obviously, this can be done in O (N select L) using a combination generation algorithm. I'm really interested in smart hacks to speed this up significantly.

Answer 1

(solution version) your problem is still NP-completed. The idea is that if we can solve your problem, then (for each size of the subset, let’s say) we could ask how many sets sums less than V and how much sums less than V-1, and the difference between these two numbers will tell us are whether the subsets that make up exactly V - so we could solve the problem of summing the subsets. [This is not complete proof, because it is a Turing contraction , not a lot of one contraction .]

However, there is simple dynamic programming that runs in O (nLV) time. [The reason for this does not prove that P = NP means that V can be exponential in input size: with n bits, you can represent values ​​up to 2 ⁿ . But assuming your V is not exponential, this is not a problem.]

Let num [v] [k] [i] denote the number of subsets of size-k from the first i elements of S that sum with v. They can be calculated as (for each i):

num[0][0][i] = 1 for v = 1 to V: for k = 1 to L: num[v][k][i] = num[v][k][i-1] + num[vS[i]][k-1][i-1] 

where S [i] is the ith element in your sequence. (Any set of sizes k that sums with v either does not use S [i], so it is counted in num [v] [k] [i-1] or uses S [i], which means that the rest of the subset has k-1 elements, uses only the first numbers i-1 in the sequence and sums up with vS [i].) Finally, count num [v] [L] [| S |] for each v less than V; what is your answer.

In addition, you can omit the third index if you do this carefully (run your loop down for each self, etc.); I just turned it on for clarity.

Answer 2

I am not ready to present a proof, but it seems that it can lend itself to a dynamic programming scheme: insert a list of subsets of size 2 into the table, use them for subsets of computers of size 3, etc., so hyou only needs to study a small collection of perspectives.

Answer 3

One optimization that comes to mind is this: order your sequence (if it is not). Select the first elements of L-1 from the very beginning, and then select the last element, such as the highest possible value (the next highest value in the sequence will give an excessively large amount). Drop the rest of the sequence because these elements can never be part of a valid subset.

After that, I guessed that it was a complete search again. But again, other optimizations are possible.

Answer 4

Isn't this just a Knapsack twist problem ? Maybe I'm wrong.

Answer 5

A dynamic programming solution for the task of summing a subset generates a table containing this answer (i.e., a Boolean table V by N, where V is the maximum number of elements and N is the maximum number of elements that can be in a set that satisfies the constraints, and each Boolean the value is true if <= N elements are combined with <= V). Therefore, if N * V is not too large for you, an acceptable fast algorithm exists. The solution of the subset of sums is only the oldest element of the set in this table, for which the number of elements is <= N / 2.

Answer 6

If these are only positive integers, you can take the confirmation step if you need to;

Take the sum of the smallest numbers L-1 in the set. If this is the sum of X, then nX must be lower than the largest element, if the problem must have a solution. Think about it, you can eliminate the other L this way ...

Answer 7

Well, on the one hand, since you set the size = L, then even if you cannot come up with something smart and just use brute force, you will have (N choose L) separate amounts in the worst case, so it's a little better than n ^^ L (well, L + 1, as you summed up each subset then).

Answer 8

It sounds like n is choosing the k category of problem. The generation of k-subsets of n is discussed in the Skiena Algorithm Design Guide, and the book suggests listing the corresponding subsets in lexicographic order (recursively, for example). Then do your sum and comparison for each subset.

If you have a sorted set, you can presumably crop impossible solutions from the solution space.

Answer 9

Perhaps the formulation of dynamic programming is amenable to PTAS FPTAS.