Find the number of subsets whose sum is less than or equal to the specified number K; Restrictions: the maximum number of elements of the set is n = 40, each should not exceed 10 ^ 16 and most importantly: the work execution time is up to 0.5 seconds and the use of not more than 20MB of RAM

Example :
Enter:
n = 5, s = 1000,
a [n] = {100, 500, 500, 1500, 1000}
Conclusion:
v = 7 + 1 (empty subset) = {{empty}, {100}, {500}, {100 + 500}, {500}, {100 + 500}, {1000}, {500 + 500}}

I tried to solve by simple enumeration of the sums of all possible subsets, but for n> 20 the work execution time grows exponentially.

If anyone can explain how this method works, I will be extremely grateful.

I found the following explanation:

  1. Split the set of integers into 2 subsets of A and B.
  2. Find all possible subsets of the number X.Yestand 2. ^ (n / 2).
  3. Now merge these 2 subproblems. Finds from x and y array of what their sum is less than or equal to S.
    • It is easy to iterate over all the elements of the array. This will take O ((2n / 2) 2) which is equivalent to O (2n).
    • For example, it makes it possible to make it less complex, to make it less complex, to make it less complex
    • Binary search here helps in reducing complexity from 2nto 2n / 2log (2n / 2) which is equivalent to 2n / 2n.
    • Thus our final running time is O (2n / 2n).

Did not quite understand the third point.

Closed due to the fact that off-topic participants Ainar-G , aleksandr barakin , 0xdb , user192664, nick_n_a Oct 30 '18 at 14:30 .

It seems that this question does not correspond to the subject of the site. Those who voted to close it indicated the following reason:

  • " Learning tasks are allowed as questions only on the condition that you tried to solve them yourself before asking a question . Please edit the question and indicate what caused you difficulties in solving the problem. For example, give the code you wrote, trying to solve the problem "- Ainar-G, aleksandr barakin, 0xdb, Community Spirit, nick_n_a
If the question can be reformulated according to the rules set out in the certificate , edit it .

    1 answer 1

    This is a classic task to illustrate the principle of "meeting in the middle", which by the way is often used in cryptography.

    This method is applied (usually) when you need to solve NP - the complete problem. The method reduces from O(2^N) to O(2^N/2) which is usually much better.

    If we need to calculate the number of sets such that F[a1,a2,...,an] = X and we are able to effectively calculate the inverse of F^-1 (i.e., ideally, the operation is reversible and reduced to just a single loop with battery). For example, for addition, this is also addition (ok subtraction), for multiplication - division (in the ring usually), for bitwise or it itself and the like. Then you can do the following operation.

    1. make up the inverse function
    2. divide the set of elements into 2 parts, so that the number of variants in each part (without intersection) is approximately the same. In the simplest case - just into 2 equal parts.
    3. make the table F^-1[X, al, al+1, ... , an] (the whole table). I will explain. The meaning of this operation is that we need to get the value of the battery, such that after adding this part of the array we will get the number X
    4. iterate over the sets {a1,a2,...,al-1} For each set we calculate F[a1,a2,...,al-1]=Y Then take from the table of paragraph 3 the set for which F^-1 = Y

    In this case, the case is canonical.

    1. We make a table for all amounts for elements 1,2...N/2
    2. We look through all the sums of the remaining list N/2+1, ... , N For each sum, we need to add to the answer the number of sums from item 1 less than k - Summ . (for this purpose it is better to use binary search).

    By the way, various works in the array can be useful.

    I do not write the code yet. There will be questions - I will add.

    • you can add, I want to know whether it is still possible to optimize the code (there is a decided version) - Melliodas
    • @Melliodas skip better your version, I think it will be easier than to compare 2 options later) - pavel