子集总和的动态编程方法

子集总和的动态编程方法

这是超级幼稚的解决方案，它仅在输入数组上生成一个幂集，然后对每个集进行迭代以查看总和是否满足给定的总数。

在时间和空间上为O（2 n）。毛。

您可以使用a的想法

Set

将所有索引存储到数组中，然后生成这些索引的所有排列，然后使用每个索引集返回到数组中并获取值。

输入项

• 目标：

  10

• 值：

  [3, 5, 5, 7]

码：

import java.util.*;import java.lang.*;import java.io.*;class SubsetSum{    public static <T> Set<Set<T>> powerSet(Set<T> originalSet)    {        Set<Set<T>> sets = new HashSet<Set<T>>();        if (originalSet.isEmpty())         { sets.add(new HashSet<T>()); return sets;        }        List<T> list = new ArrayList<T>(originalSet);        T head = list.get(0);        Set<T> rest = new HashSet<T>(list.subList(1, list.size()));         for (Set<T> set : powerSet(rest))        { Set<T> newSet = new HashSet<T>(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set);        }    return sets;    }    public static void main(String[] args)    {        Set<Integer> mySet = new HashSet<Integer>();        int[] arr={3, 5, 5, 7};        int target = 10;        int numVals = 4;        for(int i=0;i<numVals;++i)        { mySet.add(i);        }        System.out.println("Solutions: ");        for (Set<Integer> s : powerSet(mySet))         { int sum = 0; for (Integer e : s) {     sum += arr[e]; } if (sum == target) {     String soln = "[ ";     for (Integer e : s)     {         soln += arr[e];         soln += " ";     }     soln += "]";     System.out.println(soln); }        }    }}

输出量

解决方案：
[5 5]
[3 7]

现场演示

一旦了解了这一点，也许您就可以准备开始分支定界或近似方法了。