algorithm - 子集算法 - 数组子集




找到总和为特定值的所有子集 (8)

红宝石

此代码将拒绝空数组并返回带有值的正确数组。

def find_sequence(val, num)
  b = val.length
  (0..b - 1).map {|n| val.uniq.combination(n).each.find_all {|value| value.reduce(:+) == num}}.reject(&:empty?)
end

val = [-10, 1, -1, 2, 0]
num = 2

输出将是[[2],[2,0],[ - 1,1,2],[ - 1,1,2,0]]

给定一组数字:{1,3,2,5,4,9},找到总和为特定值的子集数(例如,本例中为9)。

这类似于子集求和问题,略有不同,我们必须找到这些子集的数量,而不是检查集合是否有一个总和为9的子集。 我在这里遵循子集和问题的解决方案。 但我想知道如何修改它以返回子集的数量。


同一站点geeksforgeeks还讨论了输出总和为特定值的所有子集的解决方案: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

在您的情况下,您只需要计算它们,而不是输出集。 请务必在同一页面中检查优化版本,因为它是NP-complete问题。

这个问题在之前也被提出并回答,但没有提到它是一个子集和问题: 找到所有可能的数字组合来达到给定的总和


我用java解决了这个问题。 这个解决方案非常简单。

import java.util.*;

public class Recursion {

static void sum(int[] arr, int i, int sum, int target, String s)
{   
    for(int j = i+1; j<arr.length; j++){
        if(sum+arr[j] == target){
            System.out.println(s+" "+String.valueOf(arr[j]));
        }else{
            sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j]));
        }
    }
}

public static void main(String[] args)
{   
    int[] numbers = {6,3,8,10,1};
    for(int i =0; i<numbers.length; i++){
        sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i])); 
    }

}
}

我的回溯解决方案: - 对数组进行排序,然后应用回溯。

void _find(int arr[],int end,vector<int> &v,int start,int target){
        if(target==0){
        for(int i = 0;i<v.size();i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }

    else{
        for(int i =  start;i<=end && target >= arr[i];i++){
            v.push_back(arr[i]);
            _find(arr,end,v,i+1,target-arr[i]);
            v.pop_back();
        }
    }
}

这是一个Java Solution

这是一个经典的Back跟踪问题,用于查找作为输入的整数数组或集合的所有可能子集,然后filtering那些总和为e给定target

import java.util.HashSet;
import java.util.StringTokenizer;

/**
 * Created by anirudh on 12/5/15.
 */
public class findSubsetsThatSumToATarget {

    /**
     * The collection for storing the unique sets that sum to a target.
     */
    private static HashSet<String> allSubsets = new HashSet<>();

    /**
     * The String token
     */
    private static final String token = " ";

    /**
     * The method for finding the subsets that sum to a target.
     *
     * @param input  The input array to be processed for subset with particular sum
     * @param target The target sum we are looking for
     * @param ramp   The Temporary String to be beefed up during recursive iterations(By default value an empty String)
     * @param index  The index used to traverse the array during recursive calls
     */
    public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) {

        if(index > (input.length - 1)) {
            if(getSum(ramp) == target) {
                allSubsets.add(ramp);
            }
            return;
        }

        //First recursive call going ahead selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1);
        //Second recursive call going ahead WITHOUT selecting the int at the currenct index value
        findTargetSumSubsets(input, target, ramp, index + 1);
    }

    /**
     * A helper Method for calculating the sum from a string of integers
     *
     * @param intString the string subset
     * @return the sum of the string subset
     */
    private static int getSum(String intString) {
        int sum = 0;
        StringTokenizer sTokens = new StringTokenizer(intString, token);
        while (sTokens.hasMoreElements()) {
            sum += Integer.parseInt((String) sTokens.nextElement());
        }
        return sum;
    }

    /**
     * Cracking it down here : )
     *
     * @param args command line arguments.
     */
    public static void main(String[] args) {
        int [] n =  {24, 1, 15, 3, 4, 15, 3};
        int counter = 1;
        FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0);
        for (String str: allSubsets) {
            System.out.println(counter + ") " + str);
            counter++;
        }
    }
}

它给出了与目标相加的子集的空格分隔值。

会在{24, 1, 15, 3, 4, 15, 3} 24,1,15,3,4,15,3}中打印出总和为25的子集的commma分隔值

1)24 1

2)3 4 15 3

3)15 3 4 3


这是我在JS中的动态编程实现。 它将返回一个数组数组,每个数组保持子序列求和到提供的目标值。

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20]
    tgt = 42,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));


通常的DP解决方案适用于该问题。

您可以做的一个优化是,计算特定总和存在多少解决方案的数量,而不是构成该总和的实际集合...


def total_subsets_matching_sum(numbers, sum):
    array = [1] + [0] * (sum)
    for current_number in numbers:
        for num in xrange(sum - current_number, -1, -1):
            if array[num]:
                array[num + current_number] += array[num]
    return array[sum]

assert(total_subsets_matching_sum(range(1, 10), 9)       == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)

说明

这是经典问题之一。 我们的想法是找到当前数字的可能总和数。 确实如此,只有一种方法可以将总和加到0.开始时,我们只有一个数字。 我们从目标开始(解决方案中的变量Maximum)并减去该数字。 如果可以得到该数字的总和(对应于该数字的数组元素不为零),则将其添加到与当前数字对应的数组元素中。 该程序将更容易理解

for current_number in numbers:
    for num in xrange(sum, current_number - 1, -1):
        if array[num - current_number]:
            array[num] += array[num - current_number]

当数字为1时,只有一种方法可以得出1的总和(1-1变为0,对应0的元素为1)。 所以数组就像这样(记住元素零将有1)

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

现在,第二个数字是2.我们开始从9减去2并且它无效(因为7的数组元素是零,我们跳过它)我们一直这样做直到3.当它的3,3 - 2是1并且数组元素对应于1是1并且我们将它添加到3的数组元素中,当它的2,2-2变为0并且我们将值0对应于2的数组元素。在此迭代之后,数组看起来像这样

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

我们一直这样做,直到我们处理所有数字和每次迭代后的数组看起来像这样

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]

在最后一次迭代之后,我们会考虑所有数字和获取目标的方式的数量将是与目标值对应的数组元素。 在我们的例子中,最后一次迭代后的Array [9]是8。





subset