子集和的动态规划方法

Question

给定以下输入

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

所以它与子集和问题非常相似。我对动态编程比较陌生，但在过去 3 天获得了有关 Whosebug 的帮助并在线阅读了动态编程教程并在线观看了一些视频之后。到目前为止，我已经使用了以下代码。

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。如果有人可以帮助解决问题以获得预期的结果，我将不胜感激。

也请原谅我的英语不是我的第一语言。

更新此外，我不需要打印所有可能等于分数的组合。我可以打印任何等于分数的组合，它会很好。

Answer 1

我可能会尝试一些东西。

首先，您传递了一个包含 4 个值的数组，但后来您说只有三个玩家。我认为这给您带来了一些困难。

对于我能想到的最快的编程方式，我可能会尝试这个。

public static void getSolution(int[] array, int desiredTotal) {
    for (int firstIndex = 0; firstIndex < array.size - 1; ++firstIndex) {
        getSolutionWith(array, desiredTotal, firstIndex);
    }
}

public static void getSolutionWith(int[] array, int desiredTotal, int firstIndex) {
    int lookFor = desiredTotal - array[firstIndex];
    for (int secondIndex = firstIndex + 1; secondIndex < array.size; ++secondIndex) {
        if (array[secondIndex] == lookFor) {
            System.out.printf("%d %d\n", firstIndex + 1, secondIndex + 1);
        }
    }
}

我还没有测试过这段代码，所以它可能并不完美。基本上你从 0 位置（人 1）开始，然后你看看其他人，看看第一个人的价值 + 第二个人的价值是否等于你的总和。如果是这样，你打印它们。

Answer 2

你的问题出在这部分代码

            if(arr[i] < x)
            {
                myArray[i][x] = myArray[i-1][x];
            }
            else
            {
                myArray[i][x] = myArray[i-1][x-arr[i]];
            }

你有两种情况

（在 if 内）我们已经找到了一个集合，在这种情况下，您需要将上一个结果携带到下一个。
(inside else) 相减后结果为假，但之前的结果为真。所以你需要携带那个结果。

为什么？ [3, 34, 4, 12, 5, 2]

不要忘记 DP 具有 Optimal Substructure 属性的部分。因为，找到总和是 9 我们必须找到它之前的所有总和，即 1 到 8。这正是你通过声明 W+1 行所做的。所以当我们计算 sum 为 7 时，对于前三个值我们有一个结果 [3,34,4]，我们需要将该结果带到下一层。

所以需要修改之前的代码，改成这样

           myArray[i][x] = myArray[i-1][x];//carrying previous result
            if(x>=arr[i] )
            {
                if (myArray[i][x]==1){
                    myArray[i][x]=1; 
                }
                else{
                    myArray[i][x] = myArray[i-1][x-arr[i]];
                }
            }

您还有数组索引问题。您的 i 和 x 都从 1 开始，您从不考虑实际上是您的第一个玩家的索引 0。你需要取arr[i-1]值

所以进一步的更新将是这样的，

        myArray[i][x] = myArray[i-1][x];//carrying previous result
                if(x>=arr[i-1] )
                {
                    if (myArray[i][x]==1){
                        myArray[i][x]=1; 
                    }
                    else{
                        myArray[i][x] = myArray[i-1][x-arr[i-1]];
                    }
                }

因此最终程序将如下所示

    public boolean findSolution(int[] scores, int total) {
    int W = total;
    int players = scores.length;

    boolean[][] myArray = new boolean[players + 1][total + 1];

    for (int player = 0; player <= players; player++) {
        myArray[player][0] = true;
    }
    for (int score = 1; score < total; score++) {
        myArray[0][score] = false;
    }
    for (int player = 1; player <= players; player++) {
        for (int score = 1; score <= total; score++) {
            myArray[player][score] = myArray[player - 1][score];
            if (score >= scores[player - 1]) {
                myArray[player][score] = myArray[player - 1][score
                        - scores[player - 1]]
                        || myArray[player][score];
            }
        }
    }
    return myArray[players][W];

}

现在打印结果，查看矩阵中的真值。找出设置了哪些值以及设置时间应该不难。打印这些索引以获得结果。

Answer 3

这是一个超级天真的解决方案，它只是在您的输入数组上生成一个幂集，然后遍历每个集合以查看总和是否满足给定的总数。我和 code already available on Whosebug.

一起破解了它

O(2ⁿ) 时间和 space。恶心。

您可以使用 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);
            }
        }
    }
}

输出

Solutions:
[ 5 5 ]
[ 3 7 ]

Live Demo

一旦你理解了这一点，也许你已经准备好开始分支定界法或近似法了。

Answer 4

public List<Integer> findSubsetWithSum(int[] score, int totalScore)
{
    int players = score.length;

    int[] cameFrom = new int[totalScore+1];
    int[] pickedPlayer = new int[totalScore+1];
    for (int s = 0; s <= totalScore; s++)
    {
        cameFrom[s] = -1;
        pickedPlayer[s] = -1;
    }
    cameFrom[0] = 0;
    for (int p = 0; p < players; p++)
    {
        for (int s = score[p]; s <= totalScore; s++)
        {
            if (cameFrom[s - score[p]] >= 0)
            {
                cameFrom[s] = s - score[p];
                pickedPlayer[s] = p + 1;
            }
        }
    }
    List<Integer> picked = new ArrayList<Integer>();
    for (int s = totalScore; s > 0 && cameFrom[s] >= 0; s = cameFrom[s])
    {
        picked.add(pickedPlayer[s]);
    }
    return picked;
}

子集和的动态规划方法

Dynamic Programing approach for a subset sum

java

algorithm

recursion

dynamic-programming

subset

输入

代码：

输出