如何在Java中实现子集总和问题 [英] How to implement the Sum of Subsets problem in Java

问题描述

有人知道如何通过此伪代码在Java中实现子总和问题吗?

Does anyone know how to implement the Sum-of-Subsets problem in Java from this pseudo code?

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!!!

推荐答案

首先，该算法会删除所有大于总和的数字.

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.

这篇关于如何在Java中实现子集总和问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！