مسألة مجموع المجموعات الجزئية

مسألة مجموع المجموعات الجزئية Subset sum problem هي مسألة هامة في نظرية التعقيد الحسابي و علم التعمية. يتم سرد المسألة على النحو التالي، من أجل مجموعة من الأعداد الصحيحة، هل يوجد بعض المجموعات الجزئية الغير خالية التي يكون مجموع عناصرها مساوياً للصفر؟ على سبيل المثال هل يوجد مجموعة جزئية من المجموعة التالية {−2, −3, 15, 14, 7, −10} يكون مجموع عناصرها مساوياً للصفر؟ الجواب بكل بساطة هو نعم، لأن المجموعة الجزئية {−2, −3, −10, 15} مجموعها صفر وهو أمر من الممكن التحقق منه بكل بساطة بجمع العناصر. لكن إن عملية إيجاد كل مجموعة جزئية من المجموعة الأساسية يكون مجموع جميع عناصرها ينتهي إلى الصفر يأخذ وقتاً طويلاً. هذه المسألة هي مسألة NP كاملة وربما هي من أبسط المسائل من المسائل المعقدة.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 خوارزميات تقريب زمني متعددة الحدود

Suppose all inputs are positive. An approximation algorithm to SSP aims to find a subset of S with a sum of at most T and at least r times the optimal sum, where r is a number in (0,1) called the approximation ratio.

 Simple 1/2-approximation

The following very simple algorithm has an approximation ratio of 1/2:

• Order the inputs by descending value;
• Put the next-largest input into the subset, as long as it fits there.

When this algorithm terminates, either all inputs are in the subset (which is obviously optimal), or there is an input that does not fit. The first such input is smaller than all previous inputs that are in the subset and the sum of inputs in the subset is more than T/2 otherwise the input also is less than T/2 and it would fit in the set. Such a sum greater than T/2 is obviously more than OPT/2.

 Fully-polynomial time approximation scheme

The following algorithm attains, for every $\epsilon >0$, an approximation ratio of $(1-\epsilon )$. Its run time is polynomial in n and $1/\epsilon$. Recall that n is the number of inputs and T is the upper bound to the subset sum.

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

Note that without the trimming step (the inner "for each" loop), the list L would contain the sums of all $2^{n}$ subsets of inputs. The trimming step does two things:

• It ensures that all sums remaining in L are below T, so they are feasible solutions to the subset-sum problem.
• It ensures that the list L is "sparse", that is, the difference between each two consecutive partial-sums is at least $\epsilon T/n$.

These properties together guarantee that the list L contains no more than $n/\epsilon$ elements; therefore the run-time is polynomial in $n/\epsilon$.

When the algorithm ends, if the optimal sum is in L, then it is returned and we are done. Otherwise, it must have been removed in a previous trimming step. Each trimming step introduces an additive error of at most $\epsilon T/n$, so n steps together introduce an error of at most $\epsilon T$. Therefore, the returned solution is at least ${\text{OPT}}-\epsilon T$ which is at least $(1-\epsilon ){\text{OPT}}$ .

The above algorithm provides an exact solution to SSP in the case that the input numbers are small (and non-negative). If any sum of the numbers can be specified with at most P bits, then solving the problem approximately with $\epsilon =2^{-P}$ is equivalent to solving it exactly. Then, the polynomial time algorithm for approximate subset sum becomes an exact algorithm with running time polynomial in n and $2^{P}$ (i.e., exponential in P).

Kellerer, Mansini, Pferschy and Speranza and Kellerer, Pferschy and Pisinger present other FPTAS-s for subset sum.

 انظر أيضاً

• Knapsack problem - a generalization of SSP in which each input item has both a value and a weight. The goal is to maximize the value subject to a bound on the total weight.
• Multiple subset sum problem - a generalization of SSP in which one should choose several subsets.
• 3SUM
• Merkle–Hellman knapsack cryptosystem

 للاستزادة

• قالب:Introduction to Algorithms
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.
• Lagarias, J. C.; Odlyzko, A. M. (1985-01-01). "Solving low-density subset sum problems". Journal of the ACM. 32 (1): 229–246. doi:10.1145/2455.2461. ISSN 0004-5411. S2CID 885632.
• Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.