有谁知道如何通过这个伪代码在Java中实现子集和问题？
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);
}
这真的让我感到困惑，所以如果你能添加评论那就太好了！
该程序从一组数字中找到精确的对以形成所需的总和，该程序最后还会返回唯一的对。如果没有找到确切的子集，程序还会返回最近的/最接近的子集以形成所需的总和。您可以按原样运行程序来查看演示，然后根据需要进行修改。我在这里应用的逻辑是基于给定集合中的所有数字组合来获得所需的总和，您可以参考内联注释以获取更多信息
package com.test;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
*
* @author ziya sayed
* @email : [email protected] /cdn-cgi/l/email-protection
*/
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
}
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
