子集和的动态编程方法

给出以下输入

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

所以它非常类似于子集和问题。 我对动态编程相对较新，但在获得stackoverflow的帮助并在线阅读动态编程教程并在线观看过去3天的在线video。 到目前为止，我已经提供了以下代码。

 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个多小时里，我一直试图找到这个问题的错误而没有成功。 如果有人能帮助解决问题以获得理想的结果，我将非常感激。

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

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

Answer 1

这是超级天真的解决方案，它只是在输入数组上生成一个幂集，然后迭代每个集合以查看总和是否满足给定的总和。 我将其与StackOverflow上已有的代码一起攻击。

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

您可以使用Set的概念将所有索引存储到数组中，然后生成这些索引的所有排列，然后使用每组索引然后返回到数组并获取值。

输入

• 目标： 10
• 价值观： [3, 5, 5, 7]

码：

 import java.util.*; import java.lang.*; import java.io.*; class SubsetSum { public static  Set> powerSet(Set originalSet) { Set> sets = new HashSet>(); if (originalSet.isEmpty()) { sets.add(new HashSet()); return sets; } List list = new ArrayList(originalSet); T head = list.get(0); Set rest = new HashSet(list.subList(1, list.size())); for (Set set : powerSet(rest)) { Set newSet = new HashSet(); newSet.add(head); newSet.addAll(set); sets.add(newSet); sets.add(set); } return sets; } public static void main(String[] args) { Set mySet = new HashSet(); int[] arr={3, 5, 5, 7}; int target = 10; int numVals = 4; for(int i=0;i 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]

现场演示

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

Answer 2

 public List 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 picked = new ArrayList(); for (int s = totalScore; s > 0 && cameFrom[s] >= 0; s = cameFrom[s]) { picked.add(pickedPlayer[s]); } return picked; } 

Answer 3

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

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

你有两种情况

1. （在if中）我们已经在这种情况下找到了一个集合，你需要将前一个结果带到下一个。
2. （在其他内部）减去结果后变为false，但之前的结果为true。 所以你需要携带那个结果。

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

不要忘记DP具有最佳子结构属性的部分。 因为，找到和是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]]; } } 

您还有arrays索引问题。 你的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 4

我可能会尝试一些事情。

首先，你传递的是一个包含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）开始，然后你看其他人，看看第一个人的价值+第二个人的价值是否等于你的总数。 如果是这样，你打印它们。