子集和的动态规划方法

给定以下输入

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，或者输出可以是23，因为玩家2+玩家3得分=5+5->10

所以它与子集和问题非常相似。我对动态编程相对陌生，但在获得stackoverflow的帮助后，在过去的3天里，我在线阅读了动态编程教程，并观看了一些在线视频。到目前为止，我附带了以下代码。

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个多小时里，我一直试图在这个问题上找到错误，但没有成功。如果有人能帮助解决这个问题以获得期望的结果，我将不胜感激。

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

更新此外，我不需要打印所有可能的得分相等的组合。我可以打印任何与分数相等的组合，都可以

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;
}

这是一个超级天真的解决方案，它只需在输入数组上生成一个幂集，然后对每个集进行迭代，看看总和是否满足给定的总和。我把它和StackOverflow上已有的代码一起破解了。

O（2ⁿ）在时间和空间上。总

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

输出

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

实时演示

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

您的问题在于代码的这一部分

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

有两种情况

（内部if）我们已经找到了一个集合，在这种情况下，您需要将上一个结果转移到下一个结果
（其他内部）减去后的结果为假，但之前的结果为真。所以你需要得到这个结果

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

不要忘记DP具有最优子结构特性的部分。因为，求和是9，我们必须找到它之前的所有和，意味着1到8。这正是您通过声明一个W+1行来完成的。所以，当我们计算和为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];
}

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

我可能会尝试一些事情。

首先，你在一个有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 %dn", firstIndex + 1, secondIndex + 1);
        }
    }
}

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

输入

代码：

输出

相关内容

最新更新

热门标签：