代码之家 › 专栏 › 技术社区 › sahil mehta

我们能从分区的动态解中得到子集吗?

partitioning arrays java

sahil mehta · 技术社区 · 7 年前

我想打印出一个集合的两个子集,它们给出了相同的和,这基本上就是划分问题。我正在使用动态解决方案 partition problem . 问题是,它只返回布尔答案(无论集合是否可以分区)。如何从动态规划中使用的2d表格中获取子集?

如何回溯用于获取元素的2D数组?

public class SubsetSum {
    public boolean partition(int arr[]) {
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        if (sum % 2 != 0) {
            return false;
        }

        sum = sum / 2;
        boolean[][] T = new boolean[arr.length + 1][sum + 1];

        for (int i = 0; i <= arr.length; i++) {
            T[i][0] = true;
        }

        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j - arr[i - 1] >= 0) {
                    T[i][j] = T[i - 1][j - arr[i - 1]] || T[i - 1][j];
                } else {
                    T[i][j] = T[i-1][j];
                }
            }
        }

        return T[arr.length][sum];
    }

    public static void main(String args[]) {
        SubsetSum ss = new SubsetSum();
        int arr[] = {1, 3, 5, 5, 2, 1, 1, 6};
        System.out.println(ss.partition(arr));
    }
}

1 回复 | 直到 7 年前

sahil mehta 7 年前

得到了答案。以防有人问到同样的问题。
如果partition方法返回true。S1是整数类型的ArrayList。它将存储其中一个子集的元素,比如Subset1。给定数组中的其余元素将是subset2的一部分。

if(T[input.length][total])
    {
        int i=input.length-1;
        int j=total;
        while(i!=0||j!=0)
        {
            if(T[i][j])
                i--;
            else
            {
                S1.add(input[i]);
                j-=input[i];
            }
        }
 }