search

Home  >  Q&A  >  body text

c++ - 如何实现去除所有集合内可以组成加法运算的子集

给一组数列，若数列内存在一个数等于数列内其他一些数的和，则去除那些数。此删除操作可重复操作直到无法继续找到满足条件的数进行删除。请写出一个函数，输入为整型数组，经过函数内一系列删除操作后得到一个最短数组，返回最短数组的长度。
比如{48，20，1，3，4，6，9，24}由于(4+20+24=48)所以去除4，20，24，48，余下{1,3,6,9}后，由于3+6=9，去除{3,6,9}得到{1}，由于数组长度为1，返回1

黄舟黄舟2808 days ago777

reply all(1)I'll reply

  • ringa_lee

    ringa_lee2017-04-17 15:39:03

    This problem is solved by visual inspection of the NPC. It can be divided into "two steps".

    1. Find all "additional subsets". Take each element as a possible sum and use the subset sum algorithm to solve it one by one.

    2. Find the maximum union of mutually exclusive additive subsets: refer to the set packing algorithm and use linear programming to solve it.

    The following uses Mathematica to describe the algorithm in detail.

    Find addition subset

    To enumerate all the numbers that constitute the addition formula in the set (allowing negative numbers and repeated numbers), first use the subset sum algorithm (recursion with caching) to enumerate the subsets whose sum is a given number . 

    subsetSum[lst_List, s_] := Block[{q},
  q[k_?NonPositive, x_] := {};
  q[k_?Positive, x_] := q[k, x] =
    Union[q[k - 1, x],
     If[lst[[k]] == x, {{x}}, {}],
     (Append[lst[[k]]] /* Sort) /@ q[k - 1, x - lst[[k]]]];
  q[Length[lst], s]]
    The

    code makes a recursive call to q and caches the results. For specific recursive derivation, please refer to this question. Note that the calculated addition subsets are sorted internally, and finally a union operation is performed to remove duplicates. Use case: 

    subsetSum[{1, 2, 3, 4, 5}, 8]
> {{3, 5}, {1, 2, 5}, {1, 3, 4}}

    The given number may be any element in the set in this problem, so use subsetSum to iterate through each element in the set and try to form an addition with it and the remaining elements. Finally, the duplicate combinations are removed, which is the total possible addition subset. 

    summationList[lst_List] := Union @@ Array[
   i \[Function] Map[Append[lst[[i]]] /* Sort,
     Select[subsetSum[Delete[lst, i], lst[[i]]], Length[#] > 1 &]],
   Length[lst]]

    The above code also performs an internal sorting operation on the set, because the order may be disrupted when adding sum and sum to the set. And the case where the number of addends is less than 2 is deleted. Use case: 

    summationList[{1, 2, 3, 4, 5}]
> {{1, 2, 3}, {1, 3, 4}, {1, 4, 5}, {2, 3, 5}}

    Find mutually exclusive maximum union

    After obtaining the addition subset, use weighted set packing to find the mutually exclusive maximum union among them. To describe it in linear programming language is

    $$array{text{maximize} & sum{|s_i| The sets are mutually exclusive} \ & x_i in {0, 1} & text{$x_i=1$, then select the set $i$, otherwise abandon the set $i$}}$$

    Mathematica provides built-in LinearProgramming functions: 

    pickSumList[lst_List] := Module[{sumlst},
  sumlst = summationList[lst];
  Pick[sumlst,
   LinearProgramming[
    -Length /@ sumlst,
    Outer[MemberQ[#2, #1] & /* Boole, lst, sumlst, 1],
    ConstantArray[{1, -1}, Length[lst]],
    ConstantArray[{0, 1}, Length[sumlst]],
    Integers],
   1]]

    Test

    Example of topic:

    Randomly generate a set of 16 elements.

    Find results with pickSumList and highlight elements that are sums:

    Remaining elements:

    reply
    0
  • Cancelreply