Как реализовать проблему суммы подмножеств в Java

Question

Кто-нибудь знает, как реализовать проблему Sum-of-Subsets в 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);
}

это действительно сбивает меня с толку, так что, если бы вы могли добавить комментарии, это было бы здорово !!!

Answer 1

Эта программа находит точные пары из набора чисел, чтобы сформировать желаемую сумму, программа также возвращает уникальные пары в конце. Программа также возвращает ближайшее / ближайшее подмножество для формирования желаемой суммы, если точное подмножество не найдено. Вы можете запустить программу как есть, чтобы увидеть демо, а затем выполнить модификацию, если это необходимо. Логика, которую я применил здесь, основана на всех комбинациях чисел в данном наборе, чтобы получить желаемую сумму, вы можете обратиться к встроенным комментариям для получения дополнительной информации

package com.test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author ziya sayed
 * @email : sayedziya@gmail.com
 */
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
        }

    }


}

Answer 2

Алгоритмы, закодированные в Java

Сначала алгоритм удаляет все числа, которые больше, чем сумма для начала.

Затем для наибольшего числа, меньшего суммы, он проверяет, есть ли в списке какие-либо числа, которые он может добавить к себе, чтобы получить сумму. Как только мы нашли пару, или сумма больше, чем желаемая сумма, мы можем прерваться, так как список отсортирован. Затем мы рассмотрим второе по величине число и посмотрим, сможем ли мы создать пару с этим и так далее.

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

Алгоритм выше не возвращает пары, но это тривиально добавить.