一連の数値 {1, 3, 2, 5, 4, 9} を指定して、特定の値 (この例では 9 など) になるサブセットの数を見つけます。
これは部分集合和の問題に似ていますが、集合に合計が 9 になる部分集合があるかどうかをチェックする代わりに、そのような部分集合の数を見つけなければならないというわずかな違いがあります。ここでサブセット合計問題の解決策に従ってい ます。しかし、サブセットの数を返すように変更する方法を考えています。
130080 次
18 に答える
36
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)
説明
これは古典的な問題の 1 つです。アイデアは、現在の数で可能な合計の数を見つけることです。確かに、合計を 0 にする方法は 1 つだけです。最初は、1 つの数値しかありません。目標 (ソリューション内の変数の最大値) から開始し、その数値を減算します。その数値の合計を取得できる場合 (その数値に対応する配列要素がゼロでない場合)、それを現在の数値に対応する配列要素に追加します。プログラムはこのように理解する方が簡単でしょう
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-1 が 0 になり、0 に対応する要素が 1 になります)。したがって、配列は次のようになります (要素 0 には 1 があることに注意してください)
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
ここで、2 番目の数値は 2 です。9 から 2 を引き始めますが、これは有効ではありません (7 の配列要素は 0 であるため、スキップします) 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 です。
于 2013-08-19T11:51:02.827 に答える
19
動的計画法を使用できます。アルゴリズムの複雑さはO(Sum * N)であり、 O(Sum)メモリを使用します。
C# での私の実装は次のとおりです。
private static int GetmNumberOfSubsets(int[] numbers, int sum)
{
int[] dp = new int[sum + 1];
dp[0] = 1;
int currentSum =0;
for (int i = 0; i < numbers.Length; i++)
{
currentSum += numbers[i];
for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)
dp[j] += dp[j - numbers[i]];
}
return dp[sum];
}
注: サブセットの数は 2^N の値を持つ可能性があるため、簡単に int 型をオーバーフローする可能性があります。
アルゴは正の数に対してのみ機能します。
于 2013-08-19T06:56:36.313 に答える
12
ここにあるJava Solution：
これは、入力である整数配列または集合のすべての可能な部分集合を見つけてから、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++;
}
}
}
合計するとターゲットになるサブセットの値をスペースで区切って指定します。
サブセットのカンマ区切りの値を出力します25。
{24, 1, 15, 3, 4, 15, 3}
1) 24 1
2) 3 4 15 3
3) 15 3 4 3
于 2015-05-13T17:53:22.023 に答える
6
同じサイト geeksforgeeks では、合計が特定の値になるすべてのサブセットを出力するソリューションについても説明しています: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/
あなたの場合、出力セットの代わりに、それらを数えるだけです。NP完全問題ですので、同ページ内の最適化版を必ずご確認ください。
この質問は、サブセット合計の問題であることに言及することなく、以前にスタックオーバーフローで尋ねられ、回答されました:
于 2013-08-19T03:48:04.233 に答える
5
これは ruby の私のプログラムです。これは配列を返し、それぞれが指定されたターゲット値に加算されるサブシーケンスを保持します。
array = [1, 3, 4, 2, 7, 8, 9]
0..array.size.times.each do |i|
array.combination(i).to_a.each { |a| print a if a.inject(:+) == 9}
end
于 2017-05-03T13:09:47.850 に答える
2
この問題には、通常の DP ソリューションが当てはまります。
実行できる最適化の 1 つは、その合計を構成する実際のセットではなく、特定の合計に対して存在するソリューションの数を数えることです...
于 2013-08-19T08:43:04.950 に答える
0
非常に多くのインタビューでこれが求められていることがわかったので、非常にシンプルでわかりやすいソリューションを実装しました。まず、考えられるすべての組み合わせを生成します。そこから、好きなことを行うことができます。これをチェックしてください：
public static void main(String[] args) {
int[] numbers = new int[]{1, 2, 3, 4, 5};
List<int[]> allPossibleCombinatiosForNumbers = new ArrayList<>();
for (int i = 2; i < numbers.length; i++) {
allPossibleCombinatiosForNumbers.addAll(getCombinationsOfNElements(numbers, i));
}
for (int[] combination : allPossibleCombinatiosForNumbers) {
printArray(combination);
printArrayIfNumbersSumExpectedValue(combination, 6);
}
}
private static List<int[]> getCombinationsOfNElements(int[] numbers, int n) {
int elementsKnown = n - 1;
List<int[]> allCombinationsOfNElements = new ArrayList<>();
for (int i = 0; i < numbers.length - elementsKnown; i++) {
int[] combination = new int[n];
for (int j = 0; j < n; j++) {
combination[j] = numbers[i + j];
}
allCombinationsOfNElements.addAll(generationCombinations(combination, i + elementsKnown, numbers));
}
return allCombinationsOfNElements;
}
private static List<int[]> generationCombinations(int[] knownElements, int index, int[] numbers) {
List<int[]> combinations = new ArrayList<>();
for (int i = index; i < numbers.length; i++) {
int[] combinationComplete = Arrays.copyOf(knownElements, knownElements.length);
combinationComplete[knownElements.length - 1] = numbers[i];
combinations.add(combinationComplete);
}
return combinations;
}
private static void printArray(int[] numbers) {
System.out.println();
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i] + " ");
}
}
private static void printArrayIfNumbersSumExpectedValue(int[] numbers, int expectedValue) {
int total = 0;
for (int i = 0; i < numbers.length; i++) {
total += numbers[i];
}
if (total == expectedValue) {
System.out.print("\n ----- Here is a combination you are looking for -----");
printArray(numbers);
System.out.print("\n -------------------------------");
}
}
于 2020-06-18T02:16:56.077 に答える