子集总和的动态编程方法

一尘不染

子集总和的动态编程方法

algorithm

给定以下输入

10 4 3 5 5 7

哪里

10 = Total Score

4 = 4 players

3 = Score by player 1

5 = Score by player 2

5 = Score by player 3

7 = Score by player 4

我要打印合并分数加在一起的球员，所以输出可能是 1 4因为球员1 +球员4得分= 3 + 7-> 10或输出可能是2 3，因为球员2 +球员3得分=
5 + 5-> 10

因此，它与子集和问题非常相似。我是动态编程的新手，但在获得的帮助并在线阅读了动态编程教程之后，并在过去的三天内在线观看了一些视频。到目前为止，我随附了以下代码。

class Test
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] test = {3,5,5,7};
        getSolution(test,4,10);
    }

    //pass total score, #of players (size) and the actual scores by each player(arr)
    public static int getSolution(int[] arr,int size, int total){


        int W = total;
        int n = size;
        int[][] myArray = new int[W+1][size+1];

        for(int i = 0; i<size+1; i++)
        {
            myArray[i][0] = 1;
        }
        for(int j =1; j<W+1; j++)
        {
            myArray[0][j] = 0;
        }

        for(int i =1; i<size+1; i++)
        {
            for(int x=1; x<W+1; x++)
            {
                if(arr[i] < x)
                {
                    myArray[i][x] = myArray[i-1][x];
                }
                else
                {
                    myArray[i][x] = myArray[i-1][x-arr[i]];
                }
            }
        }

        return myArray[n][W];
    }

}

由于某种原因，我没有得到预期的结果。过去7多个小时，我一直试图在此问题中找到错误，但未成功0。如果有人可以帮助解决该问题以获得期望的结果，我将不胜感激。

另外请原谅我的英语不是我的母语。

更新我也不需要打印等于分数的所有可能组合。我可以打印等于分数的任何组合，这样就可以了。

阅读 230

2020-07-28

共1个答案

一尘不染

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

在时间和空间上为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]

现场演示

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

2020-07-28