c# - 组合、幂集 不知道从哪里开始

Question

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

这是设置，我在 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，它将是 child 5、6、7，我会忽略 8。

子组合没有固定的大小，可以组合起来等于父组合。

所以做了一些研究，看来我需要为每个 parent 获得所有 child 的权力集。然后从那里我可以总结他们的总数，看看他们中的任何一个是否等于 parent 。但是，如果我错了请纠正我，但如果集合中有 N 个项目，则幂集将包含 2^N 个组合。

其中一些 parent 有超过 750 个 child ，2^750 是一个非常非常大的数字。我主要是 .NET/SQL Server 人员，但愿意尝试人们认为适合这项工作的任何技术。

那么几个问题。

1) 我应该继续尝试找出每个 parent 的权力集还是我用那个树错误的树？
2) 这是一个已经被计算出来的算法，我只是在谷歌上找不到它吗？3) 假设这可以做到，那么解决它的正确方法是什么？

Answer 1

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

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)。大家可以根据问题来选择。