如何在 Java 中实现子集总和问题
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5585104/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to implement the Sum of Subsets problem in Java
提问by Stylzs05
Does anyone know how to implement the Sum-of-Subsets problem in Java from this pseudo code?
有谁知道如何从这个伪代码在 Java 中实现 Sum-of-Subsets 问题？
w = an array of positive integers sorted in non-decreasing order.
W = the target sum value
include = an array or arraylist of the solutions who's weight adds up to W. After the print statement, this array can be deleted so that it can store the next solution.
weight = weight of elements in the include array.
total = weight of the remaining elements not in the include array.
public static void sum_of_subsets(index i, int weight, int total)
{
if(promising(i))
{
if(weight == W)
{
System.out.print(include[1] through include[i]);
}
else
{
include[i + 1] = "yes"; //Include w[i + 1]
sum_of)subsets(i + 1, weight + w[i + 1], total - w[i + 1]);
include[i + 1] = "no"; //Do not include w[i + 1]
sum_of_subsets(i + 1, weight, total - w[i + 1]);
}
}
}
public static boolean promising(index i);
{
return (weight + total >= W) && (weight == W || weight + w[i + 1] <= W);
}
this is really baffling me, so if you could add comments that would be great!!!
这真的让我莫名其妙，所以如果你能添加评论那就太好了！！！
采纳答案by jberg
First the algorithm removes all numbers that are larger than the sum to begin with.
首先，算法删除所有大于总和的数字。
Then for the largest number smaller than the sum, it checks if there are any numbers in the list that it can add to itself to get the sum. Once we have either found a pair, or the sum is greater than the desired sum, we can break since the list is sorted. We then consider the second largest number and see if we can make a pair with that, and so on.
然后对于小于总和的最大数字，它检查列表中是否有任何数字可以添加到自身以获得总和。一旦我们找到一对，或者总和大于所需的总和，我们就可以中断，因为列表已排序。然后我们考虑第二大数字，看看我们是否可以与它配对，依此类推。
/**
* This will find how many pairs of numbers in the given array sum
* up to the given number.
*
* @param array - array of integers
* @param sum - The sum
* @return int - number of pairs.
*/
public static int sumOfSubset(int[] array, int sum)
{
// This has a complexity of O ( n lg n )
Arrays.sort(array);
int pairCount = 0;
int leftIndex = 0;
int rightIndex = array.length - 1;
// The portion below has a complextiy of
// O ( n ) in the worst case.
while (array[rightIndex] > sum + array[0])
{
rightIndex--;
}
while (leftIndex < rightIndex)
{
if (array[leftIndex] + array[rightIndex] == sum)
{
pairCount++;
leftIndex++;
rightIndex--;
}
else if(array[leftIndex] + array[rightIndex] < sum)
{
leftIndex++;
}
else
{
rightIndex--;
}
}
return pairCount;
}
The algorithm above does not return the pairs, but that is trivially to add.
上面的算法不返回对，但这很容易添加。
回答by Ziya Sayed
This program finds the exact pairs from a set of numbers to form the desired sum, the program also returns the unique pairs in the end. The program also returns a nearest/closest subset to form the desired sum if no exact subset is found. You can run the program as is to see the demo and then do the modification if needed. The logic I have applied here is based on all combinations of numbers in a given set to get the desired sum, you can refer to inline comments for further information
该程序从一组数字中找到精确的对以形成所需的总和，该程序最后还返回唯一的对。如果没有找到确切的子集，程序还会返回最近/最接近的子集以形成所需的总和。您可以按原样运行程序以查看演示，然后根据需要进行修改。我在这里应用的逻辑是基于给定集合中数字的所有组合来获得所需的总和，您可以参考内联注释以获取更多信息
package com.test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
*
* @author ziya sayed
* @email : [email protected]
*/
public class SumOfSubsets{
// private static int[] numbers= {1,1,2,2,3,4};//set of numbers
private static int[] numbers= {18,17,1};//set of numbers
// private static final int SUM = 4;//desired sum
private static final int SUM = 20;//desired sum
public static void main(String[] args) {
String binaryCount="";
int[] nos=new int[numbers.length];
//input set, and setting binary counter
System.out.print("Input set numbers are : ");
for (int no : numbers) {
if (no<=SUM) {
System.out.print(no+" ");
nos[binaryCount.length()]=no;
binaryCount+=1; //can we use sring builder or string.format
}
}
System.out.println();
Arrays.sort(nos);//sort asc
int totalNos = binaryCount.length();
String subset=""; //chosen subset
int subsetSum=0;//to temp hold sum of chosen subset every iteration
String nearestSubset="";//chosen closest subset if no exact subset
int nearestSubsetSum=0;//to hold sum of chosen closest subset
Set<String> rs = new HashSet<String>();//to hold result, it will also avoide duplicate pairs
for (int i = Integer.parseInt(binaryCount, 2) ; i >0;i-- ) {//for all sum combinations
// System.out.println(i);
binaryCount=String.format("%1$#" + totalNos + "s", Integer.toBinaryString(i)).replace(" ","0");//pad 0 to left if number is less than 6 digit binary for proper combinations
subset="";
subsetSum=0;
for (int j=0 ;j<totalNos; j++) {//for active combinations sum
if (binaryCount.charAt(j)=='1') {
subset+=nos[j]+" ";
subsetSum+=nos[j];
}
}
if (subsetSum == SUM) {
// System.out.println(subset);//we can exit here if we need only one set
rs.add(subset);
}
else{//use this for subset of numbers with nearest to desired sum
if (subsetSum < SUM && subsetSum > nearestSubsetSum && rs.isEmpty()) {
nearestSubsetSum = subsetSum;
nearestSubset = subset;
}
}
}
if (rs.isEmpty()) {
System.out.println("Nearest Subset of "+SUM);
System.out.println(nearestSubset);
}
else{
System.out.println("Exact Subset of "+SUM);
System.out.println(rs);//unique sub sets to remove duplicate pairs
}
}
}
