一个子集和动态规划方法 [英] Dynamic Programing approach for a subset sum
问题描述
由于以下输入
10 3 4 5 7
其中，
10 =总分
4 = 4的球员
3 =得分的球员1
5 =得分的球员2
5 =得分的球员3
7 =得分的球员4
我要打印的球员是谁的组合得分增加了总让输出可
1 4 ，因为球员1 +播放器的4分= 3 + 7 - > 10或输出可以是2 3，因为球员2 + 3的球员得分= 5 + 5 - > 10
因此，它是十分相似的子集和问题。我是比较新的动态编程，但得到的计算器的帮助，阅读动态编程教程在线观看一些影片在线为近3天。下面code我来了这么远。</ P>
类测试
{
公共静态无效的主要（字串[] args）抛出java.lang.Exception的
{
INT []测试= {3,5,5,7};
getSolution（测试，4,10）;
}
//由每个玩家传递总分，移位#of玩家（大小）与实际的分数（改编）
公共静态INT getSolution（INT []编曲，诠释大小，诠释总计）{
INT W =总;
INT N =大小;
INT [] [] = myArray的新INT [W + 1] [大小+ 1];
的for（int i = 0; I＆LT;大小+ 1;我++）
{
myArray的[I] [0] = 1;
}
对于（INT J = 1; J＆LT; W + 1; J ++）
{
myArray的[0] [J] = 0;
}
的for（int i = 1; I＆LT;大小+ 1;我++）
{
为（中间体X = 1; X＆所述; W + 1; X ++）
{
如果（改编[1] - ; x）的
{
myArray的[I] [X] = myArray的[I-1] [X];
}
其他
{
myArray的[I] [X] = myArray的[I-1] [X-改编[Ⅰ]];
}
}
}
返回myArray的[n]的[W];
}
}
出于某种原因，我没有得到预期的结果。我一直试图找到这个问题过去7+小时的bug没有0成功。我会强烈AP preciate，如果有人可以帮助解决问题，以获得期望的结果。
另外，请原谅我的英语不是我的第一语言。
更新 另外我不需要打印等于得分所有可能的组合。我可以打印等于得分的任意组合，这将是罚款。
下面是超级幼稚的解决方案，它只是产生一个电源上的输入数组，然后遍历每个集合，看看如果和给定的总满足设定。我与 code砍死在一起已经可以在计算器。
O（2 N ），在时间和空间。格罗斯。
您可以使用的想法设置所有索引存储到你的数组，然后生成这些索引的所有排列，然后用每一组索引然后去回到您的阵列和得到的值。
输入
- 目标：
10 - 值：
[3，5，5，7]
code：
进口的java.util。*;
进口的java.lang。*;
进口java.io. *;
类SubsetSum
{
公共静态＆LT; T＆GT;设置＆LT;设置＆LT; T＆GT;＆GT; Powerset的（集＆LT; T＆GT; originalSet）
{
设置＆LT;设置＆LT; T＆GT;＆GT;套=新的HashSet＆LT;设置＆LT; T＆GT;＆GT;（）;
如果（originalSet.isEmpty（））
{
sets.add（新的HashSet＆LT; T＆GT;（））;
返回套;
}
名单＆LT; T＆GT;名单=新的ArrayList＆LT; T＆GT;（originalSet）;
牛逼头= list.get（0）;
设置＆LT; T＆GT;其余部分为新的HashSet＆LT; T＆GT;（list.subList（1，则为list.size（）））;
对于（集＆LT; T＆GT;设置：幂（休息））
{
设置＆LT; T＆GT; newSet =新的HashSet＆LT; T＆GT;（）;
newSet.add（头）;
newSet.addAll（套）;
sets.add（newSet）;
sets.add（套）;
}
返回套;
}
公共静态无效的主要（字串[] args）
{
设置＆LT;整数GT; MYSET =新的HashSet＆LT;整数GT;（）;
INT []改编= {3,5，5,7};
INT目标= 10;
INT numVals = 4;
的for（int i = 0; I＆LT; numVals ++ I）
{
mySet.add（ⅰ）;
}
的System.out.println（方案）;
对于（集＆LT;整数GT; S：幂（MYSET））
{
INT总和= 0;
对于（整数e：S）
{
总和+ = ARR [E]
}
如果（总和==目标）
{
字符串SOLN =[;
对于（整数e：S）
{
SOLN + = ARR [E]
SOLN + =;
}
SOLN + =];
的System.out.println（溶液）;
}
}
}
}
输出
解决方案：
[5]
[3 7]
一旦你理解了这一点，也许你就可以开始分支限界或近似的方法。
Given the following Input
10 4 3 5 5 7
Where
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
I am to print players who's combine score adds to total so output can be
1 4 because player 1 + player 4 score = 3 + 7 -> 10 or output can be 2 3 because player 2 + player 3 score = 5 + 5 -> 10
So it is quite similar to a subset sum problem. I am relatively new to dynamic programing but after getting help on stackoverflow and reading dynamic programing tutorials online and watch few videos online for past 3 days. The following code i have come with so far.
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];
}
}
For some reason i am not getting expected result. I have been trying to find bug in this issue for past 7+ hours without 0 success. I would highly appreciate it if someone can help fix the issue to get the desired result.
Also please forgive my English it is not my first language.
Update Also i do not need to print all possible combinations that equal the score. I can print any combination that equals the score and it will be fine.
Here's the super naive solution that simply generates a power set on your input array and then iterates over each set to see if the sum satisfies the given total. I hacked it together with code already available on StackOverflow.
O(2n) in time and space. Gross.
You can use the idea of a Set to store all indices into your arrays, then generate all permutations of those indices, and then use each set of indices to then go back into your array and get the values.
Input
- Target:
10 - Values:
[3, 5, 5, 7]
Code:
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);
}
}
}
}
Output
Solutions:
[ 5 5 ]
[ 3 7 ]
Once you understand this, perhaps you are ready to begin branch and bound or approximation approaches.
这篇关于一个子集和动态规划方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
