组合，力量集甚至不知道从哪里开始

本文关键字：开始 不知道 力量 组合 | 更新日期: 2023-09-27 18:08:27

我有这个问题，我希望人们能指出我在正确的方向，因为我甚至不知道从哪里开始。

下面是设置，我在SQL Server中有两个表，表A是汇总表，表B是详细信息表，所以像这样: 
Table A
ParentID        Total Amount
1               100
2               587

Table B
ParentID        ChildID         Amount
1               1               8
1               2               7
1               3               18
1               4               93
2               5               500
2               6               82
2               7               5
2               8               10

因此，对于每个ParentID，我需要提出的孩子的组合，他们的金额的总和等于父的总金额。

对于ParentID 1(100)它将是ChildIDs 2和4(7 + 93)我将忽略ChildIDs 1和3

对于ParentID 2，它将是子元素5,6,7，我将忽略8。

没有固定大小的子组合，这些子组合可以与父组合相等。

所以做了一些研究，似乎我需要得到每个家长的所有孩子的幂集。然后我可以把它们的总金额加起来，看看是否有哪个等于父结点。但是，如果我错了，请纠正我，但如果集合中有N个项目，那么Power set将由2^N个组合组成。

有些父母有超过750个孩子，2^750是一个非常非常大的数字。我主要是一个。net/sql Server家伙，但我愿意尝试人们认为适合工作的任何技术。

有几个问题。

1)我是否应该沿着试图找出每个父母的权力集的路径走下去，或者我这样做是错误的?
2)这是一个已经被计算出来的算法，我只是在谷歌上做了一个糟糕的工作?3)假设这是可以做到的，解决它的正确方法是什么?

组合，力量集甚至不知道从哪里开始

该问题可约化为子集问题，子集问题可约化为简单的背包问题。有一个动态规划的解决方案:-

W = knapsack capacity = Total Amount of parent.
item weight = item cost = child amount.
maximize profit and if W = profit then there exists a subset else not.

利用kanpsack的DP解求解此问题，并通过回溯得到结果。

这里有一个JAVA的解决方案，也许你可以转换成c#:-

public class SubSetSum {
    static int[][] costs;
    public static void calSets(int target,int[] arr) {
        costs = new int[arr.length][target+1];
        for(int j=0;j<=target;j++) {
            if(arr[0]<=j) {
                costs[0][j] = arr[0]; 
            }
        }
        for(int i=1;i<arr.length;i++) {
            for(int j=0;j<=target;j++) {
                costs[i][j] = costs[i-1][j];
                if(arr[i]<=j) {
                    costs[i][j] = Math.max(costs[i][j],costs[i-1][j-arr[i]]+arr[i]);
                }
            }
        }
        System.out.println("total amount: "+costs[arr.length-1][target]);
       if(costs[arr.length-1][target]==target) {
           System.out.println("Sets :");
           printSets(arr,arr.length-1,target,"");
       } 
       else System.out.println("No such Set found");
    } 
    public static void printSets(int[] arr,int n,int w,String result) {

        if(w==0) {
            System.out.println(result);
            return;
        }
        if(n==0) {
           System.out.println(result+","+0);
            return; 
        }
        if(costs[n-1][w]==costs[n][w]) {
            printSets(arr,n-1,w,new String(result));
        }
        if(arr[n]<=w&&(costs[n-1][w-arr[n]]+arr[n])==costs[n][w]) {
            printSets(arr,n-1,w-arr[n],result+","+n);
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,8,9,7};
        calSets(10,arr);
    }
}

注意:-

在某些情况下，暴力破解比DP更可行，因为对于DP = O(ParentAmount*totalchildren)，时间复杂度，而对于暴力破解 = O(2^n)和空间复杂度 = O(1)，时间复杂度。你可以根据问题选择。

一些研究告诉我，你可以用N*2^ p来解决这个问题，其中N是子节点的数量，p是存储最大数字所需的位数。看，说，这里:http://en.wikipedia.org/wiki/Subset_sum_problem Polynomial_time_approximate_algorithm

=============================================

只要每个父节点的子节点数量很小，那么算出幂集是可以的，但是注意N个子节点的幂集是2^ N，它的增长非常快。2^750太大了，大约是10^225。

有很多函数用于查找powerset，我主要使用Java，我知道在Guava中有一个，我想在Apache Commoms Math中也有一个。构造一个能量集并不难，你可以直观地把它想象成一个深度为N的二叉树，其中每一层都是"我是否包含这个元素是/否"。

我不是用c#写的，而是用伪代码写的

Set<Set<Object>> Powerset(Set<Set<Object>> powerset, Object newItem){
    Set<Set<Object>> newSet = powerset.clone();
    for (Set<Object> set : newSet){
        set.add(newItem)
    }
    return newSet.addAll(powerset)
}

所以这取N个元素的幂集，返回N+1个元素的幂集。因此，您可以反复调用它以从空集开始构建powerset。

对于较大数目的子集合，使用相同的函数，而不是构建powerset，但删除总和超过目标的集合。(很明显，它是单调递增的，所以一旦超过了目标，就不能再继续下去了。例:假设Object.hasValue()返回一个数字，那么做:

Set<Set<Object>> Powerset(Set<Set<Object>> powerset, Object newItem, int target){
    Set<Set<Object>> newSet = powerset.clone();
    for (Set<Object> set : newSet){
        set.add(newItem)
    }

    Set<Set<Object>> result = new Set<Set<Object>>();
    for(Set<Object> set : newSet){
        int sum = 0;
        for(Object o : set){
            sum += o.hasvalue();
        }
        if(sum <= target){
            result.add(set)
        }
    }
    return result.addAll(powerset);
}

各种优化是可能的(例如，你应该先添加最大的数字，因为如果你尽早排除数字，它是最快的。)(如果有一个比目标大的数字，如果你先做，你只需要把它加到一个集合中，但如果你最后做，你只需要把它加到2^n-1个集合中)。您还可以使Set直接携带其组件的和，从而消除sum循环，并且您可以通过将其存储为指向其父元素的元素的树来提高空间复杂性，并执行DFS，这样您一次只有树的一个分支在内存中，并且只保留成功的分支。

如果有些父母有750个孩子，你就没时间了。如果你想在太阳熄灭之前得到答案，你应该研究某种并行云计算解决方案。

2^750 = 5922386521
        532855740161817506647119
        732883018558947359509044
        845726112560091729648156
        474603305162988578607512
        400425457279991804428268
        870599332596921062626576
        000993556884845161077691
        136496092218188572933193
        945756793025561702170624

现在，让我们假设我们真的很幸运，就像中彩票一样幸运，并且很早就找到了正确的组合。

现在，让我们假设我们有一台快速的计算机，每秒可以计算10亿次。

它会取像

这样的东西
6.332987 * 10^135 years

找到答案。这仍然是一段难以想象的漫长时间。你可以这样想，

4.52356 * 10^125 ages of the universe.

或者更确切地说，比宇宙的年龄乘以宇宙中原子的数量还要长。好长一段时间。

http://xkcd.com/287/

这是一些猜测，但我怀疑宇宙中没有足够的材料来制造足够的计算机来并行计算，以便在太阳耗尽燃料之前完成计算。(在现有技术范围内)

我建议放弃蛮力设置方法。电脑是很快的，但还没有那么快。

实际上你的情况并不像2^750分析显示的那么可怕。放弃幂集解，转而使用动态规划。其中一个选项可能像这样:

public static IEnumerable<int> FindSet(IEnumerable<int> amounts, int target)
{
    var results = new Dictionary<int, List<int>>();
    results[0] = new List<int>();
    foreach(var amount in amounts)
    {
        for(int i = 0; i <= target; i++)
        {
            if(!results.ContainsKey(i) || results[i].Contains(amount))
                continue;
            var combination = new List<int>(results[i]);
            combination.Add(amount);
            if (i + amount == target)
                return combination;
            results[i + amount] = combination;
        }
    }
    return null;
}

前提是我们一开始就说我们知道如何用空集合得到一个等于0的和。然后，对于每个可用的量，我们说，如果我们知道如何在不使用amount的情况下得到n的和，那么我们现在也知道如何通过取之前的结果并加上amount来得到n+amount的和。

从循环中可以看到，它以O(NK)阶运行，其中N是集合中值的数量，K是目标和。比O(2^N)好多了。

这只是给出一个算法的草图。可能还有很多性能调整的空间。特别是列表可以用某种支持树结构的"Node"类代替。

对于我所说的Node类的概述，如下所示:

public class Node
{
    public int Value;
    public Node Parent;
    public List<int> ToList()
    {
        if(Parent == null)
        {
            return new List<int> { Value };
        }
        var result = Parent.ToList();
        result.Add(Value);
        return result;
    }
}

那么你就不用一直复制列表了

相关文章：