组合，动力设置甚至都不知道从哪里开始 [英] Combinations, Power Sets No Idea where to even start

问题描述

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

I have this problem I was hoping people could point me in the right direction of figuring out because I dont even know where to start.

这里是设置，我在SQL Server中有两个表，表A是摘要表，表B是详细信息表，所以类似这样:

Here's the setup, I have two tables in SQL Server, Table A is a summary table, Table B is a details table, so something like this:

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，我需要得出其金额之和等于父项总金额的子项的组合.

So for each ParentID, I need to come up with the combination of children whose Sums of their Amount equals the Total Amount of the Parent.

因此对于ParentID 1(100)，它将是ChildID 2和4(7 + 93)，而我将忽略ChildID 1和3.

So for ParentID 1 (100) it would be ChildIDs 2 and 4 (7 + 93) and I would just ignore ChildIDs 1 and 3.

对于ParentID 2，它将是孩子5、6、7，而我将忽略8.

For ParentID 2 it would be the children 5, 6, 7 and I would ignore 8.

子级组合没有固定大小，可以组合成等于父级.

There is no fixed size to the children combinations that can be combined to equal the Parent.

因此，进行一些研究，看来我需要获取每个父级的所有子级的幂集.然后，从那里我可以总结它们的总金额，看看它们中的任何一个是否等于父项.但是，如果我错了，但如果集合中有N个项目，请纠正我，然后功率集将由2 ^ N个组合组成.

So doing some research, it appears I need to get the Power Set of all the children for each Parent. Then from there I can sum up their total amounts and see if any of them equal the Parent. However, correct me if I'm wrong but if there are N items in the set, then the Power Set would consist of 2^N number of combinations.

其中一些父母有750多个孩子，而2 ^ 750的数目非常非常大.我主要是.NET/SQL Server专家，但愿意尝试人们认为合适的任何技术.

Some of these parents have over 750 children and 2^750 is a very very very large number. I'm mostly a .NET/SQL Server guy but am open to trying any technologies that people would think are right for the job.

有几个问题.

1)我应该沿着试图找出每个父代的Power Set的方法走下去还是还是在树错了树呢?
2)这是不是已经找到了一种算法，而我在Google上找到它却做得很糟糕? 3)假设可以做到，那么解决该问题的正确方法是什么?

1) Should I go down the path of trying to figure out the Power Set for each parent or am I barking up the wrong tree with that?
2) Is this an alogrithm that has already been figured out and I'm just doing a poor job finding it on Google? 3) Assuming this can be done, what would be the right approach to solving it?

推荐答案

该问题可简化为子集问题，可以将其简化为简单的背包问题. 有一个针对该问题的动态编程解决方案:-

The problem is reducable to subset problem which can be reduced to simple knapsack problem. There is a dynamic programming solution to the problem :-

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.

使用背包的DP解决方案解决此问题并通过回溯获得结果.

Use DP solution of kanpsack to solve this problem and get result by backtracking.

这是JAVA中的解决方案，也许您可​​以转换为C#:-

Here is a solution in JAVA maybe you can convert to 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的空间和时间复杂度 = O(ParentAmount*totalchildren)，而蛮力的时间复杂度 = O(2^n)和空间复杂度 = O(1).您可以根据问题选择.

In some cases brute force is more feasible than DP as space and time complexity for DP = O(ParentAmount*totalchildren) and whereas time complexity for brute force = O(2^n) and space complexity = O(1). You may choose according to the problem.

这篇关于组合，动力设置甚至都不知道从哪里开始的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！