4

数値の配列と配列要素を合計する合計のリストがある場合、どの要素が合計に含まれているかを判断するための最も効果的なアプローチ (または少なくともブルート フォース ハックではない) は何ですか?

簡単な例は次のようになります。

配列 = [6, 5, 7, 8, 6, 12, 16] 合計 = [14, 24, 22]

そして私は知りたい：

14には8、6が含まれます

24 には 5、7、12 が含まれます

22には6、16が含まれます

function matchElements(arr, sums) {
    var testArr;
    function getSumHash() {
        var hash = {},
            i;
        for (i = 0; i < sums.length; i++) {
            hash[sums[i]] = [];
        }
        return hash;
    }
    sums = getSumHash();
    // I don't have a good sense of where to start on what goes here...
    return sumHash;
}

var totals = matchElements([6, 5, 7, 8, 6, 12, 16], [14,24,22]),
    total;

for (total in totals) {
   console.log(total + "includes", totals[total])
}

http://jsfiddle.net/tTMvP/

常に少なくとも 1 つの正しい答えがあることを知っています。数字がチェックアウトされることだけが重要です。重複があるインデックスをペアにする必要はありません。合計に関連する値だけです。このような問題を解決するための確立された機能はありますか?

これは、私がソリューションを書いている言語であるため、javascript の質問にすぎません。これは、Javascript でフィルタリングされた一般的な数学関連の質問です。これが適切なフォーラムでない場合は、適切なスタック交換サイトへのリダイレクトを歓迎します。

4

3 に答える 3

2

わかりました、私を呪います、これは私のノックアップです、改善を歓迎します:)

これはビンパッキング問題またはナップザックの問題だと思います

Javascript

一般Power Set機能

function powerSet(array) {
    var lastElement,
        sets;

    if (!array.length) {
        sets = [[]];
    } else {
        lastElement = array.pop();
        sets = powerSet(array).reduce(function (previous, element) {
            previous.push(element);
            element = element.slice();
            element.push(lastElement);
            previous.push(element);

            return previous;
        }, []);
    }

    return sets;
}

累乗セットのコピーを減らします。つまり、[6, 8] と [8, 6] は同じではありません。

function reducer1(set) {
    set.sort(function (a, b) {
        return a - b;
    });

    return this[set] ? false : (this[set] = true);
}

主な機能は、ビンの一致を取得し、使用済みのアイテムを削除し、すすぎ、繰り返します

function calc(bins, items) {
    var result = {
            unfilled: bins.slice(),
            unused: items.slice()
        },
        match,
        bin,
        index;

    function reducer2(prev, set) {
        if (!prev) {
            set.length && set.reduce(function (acc, cur) {
                acc += cur;

                return acc;
            }, 0) === bin && (prev = set);
        }

        return prev;
    }

    function remove(item) {
        result.unused.splice(result.unused.indexOf(item), 1);
    }

    for (index = result.unfilled.length - 1; index >= 0; index -= 1) {
        bin = result.unfilled[index];
        match = powerSet(result.unused.slice()).filter(reducer1, {}).reduce(reducer2, '');
        if (match) {
            result[bin] = match;
            match.forEach(remove);
            result.unfilled.splice(result.unfilled.lastIndexOf(bin), 1);
        }
    }

    return result;
}

これらは私たちのアイテムとそれらを詰める必要があるビンです

var array = [6, 5, 7, 8, 6, 12, 16],
    sums = [14, 24, 22];

console.log(JSON.stringify(calc(sums, array)));

出力

{"14":[6,8],"22":[6,16],"24":[5,7,12],"unfilled":[],"unused":[]}

jsfiddleについて

于 2014-02-21T08:38:17.703 に答える
2

これが制約プログラミング システム (ここでは MiniZinc) でどのようにエンコードされるかを示すことは有益かもしれません。

これが完全なモデルです。http://www.hakank.org/minizinc/matching_sums.mznでも入手できます。

int: n;
int: num_sums;
array[1..n] of int: nums; % the numbers
array[1..num_sums] of int: sums; % the sums

% decision variables

% 0/1 matrix where 1 indicates that number nums[j] is used
% for the sum sums[i]. 
array[1..num_sums, 1..n] of var 0..1: x;

solve satisfy;

% Get the numbers to use for each sum
constraint
   forall(i in 1..num_sums) (
      sum([x[i,j]*nums[j] | j in 1..n]) = sums[i]
   )
;

output 
[
   show(sums[i]) ++ ": " ++ show([nums[j] | j in 1..n where fix(x[i,j])=1]) ++ "\n" 
    | i in 1..num_sums
];

%% Data
n = 6;
num_sums = 3;
nums = [5, 7, 8, 6, 12, 16];
sums = [14, 24, 22];

行列 "x" は興味深い部分で、数値 "nums[j]" が数値 "sums[i]" の合計に使用されている場合、x[i,j] は 1 (true) です。

この特定の問題には、16 の解決策があります。

....
14: [8, 6]
24: [8, 16]
22: [6, 16]
----------
14: [6, 8]
24: [6, 5, 7, 6]
22: [6, 16]
----------
14: [6, 8]
4: [5, 7, 12]
22: [6, 16]
----------
14: [6, 8]
24: [6, 6, 12]
22: [6, 16]
----------
14: [6, 8]
24: [8, 16]
22: [6, 16]
----------
...

2 つの 6 があるため、これらは明確な解決策ではありません。たった 1 つの 6 で、2 つの解があります。

14: [8, 6]
24: [5, 7, 12]
22: [6, 16]
----------
14: [8, 6]
24: [8, 16]
22: [6, 16]
----------

余談ですが、最初にこの問題を読んだとき、使用する数値を最小化 (または最大化) することが目的なのかどうかわかりませんでした。いくつかの変数と制約を追加するだけで、モデルをその目的にも使用できます。最小数の数字を使用するソリューションは次のとおりです。

s: {6, 8, 16}
14: [8, 6]
24: [8, 16]
22: [6, 16]
Not used: {5, 7, 12}

逆に、使用される数字の最大数 (ここでは、「s」で 6 が 1 回だけカウントされるため、すべての数字が使用されます):

s: {5, 6, 7, 8, 12, 16}
14: [8, 6]
24: [5, 7, 12]
22: [6, 16]
Not used: {}

拡張された MiniZinc モデルは、http://www.hakank.org/minizinc/matching_sums2.mzn から入手できます。

(余談 2: xkcd レストランの問題についてのコメントがありました。この問題のより一般的な解決策を次に示します: http://www.hakank.org/minizinc/xkcd.mzn。これは現在のマッチング問題の変形であり、主な違いは次のとおりです。このマッチング問題のように、料理は 0..1 だけでなく、複数回数えることができます。)

于 2014-02-21T18:33:54.143 に答える
1

サブセット合計の問題はnp完全ですが、疑似多項式時間動的計画法ソリューションがあります:-

1.calculate the max element of the sums array
2. Solve it using knapsack analogy
3. consider knapsack capacity = sums[max]
4. items as arr[i] with weight and cost same.
5. maximize profit
6. Check whether a sum can be formed from sums using CostMatrix[sums[i]][arr.length-1]==sums[i]

これは同じJava実装です:-

public class SubSetSum {
    static int[][] costs;

    public static void calSets(int target,int[] arr) {

        costs = new int[arr.length][target+1];
        for(int j=0;j<=target;j++) {
            if(arr[0]<=j) {

                costs[0][j] = arr[0]; 
            }
        }
        for(int i=1;i<arr.length;i++) {

            for(int j=0;j<=target;j++) {
                costs[i][j] = costs[i-1][j];
                if(arr[i]<=j) {
                    costs[i][j] = Math.max(costs[i][j],costs[i-1][j-arr[i]]+arr[i]);
                }
            }

        }

       // System.out.println(costs[arr.length-1][target]);
       /*if(costs[arr.length-1][target]==target) {
           //System.out.println("Sets :");
           //printSets(arr,arr.length-1,target,"");
       } 

       else System.out.println("No such Set found");*/

    } 

    public static void getSubSetSums(int[] arr,int[] sums) {

        int max = -1;
        for(int i=0;i<sums.length;i++) {
            if(max<sums[i]) {
                max = sums[i];
            }
        }

        calSets(max, arr);

        for(int i=0;i<sums.length;i++) {
            if(costs[arr.length-1][sums[i]]==sums[i]) {
                System.out.println("subset forming "+sums[i]+":");
                printSets(arr,arr.length-1,sums[i],"");
            }
        }




    }

    public static void printSets(int[] arr,int n,int w,String result) {


        if(w==0) {
            System.out.println(result);
            return;
        }

        if(n==0) {
           System.out.println(result+","+arr[0]);
            return; 
        }

        if(costs[n-1][w]==costs[n][w]) {
            printSets(arr,n-1,w,new String(result));
        }
        if(arr[n]<=w&&(costs[n-1][w-arr[n]]+arr[n])==costs[n][w]) {
            printSets(arr,n-1,w-arr[n],result+","+arr[n]);
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 7, 8, 6, 12, 16};
        int[] sums = {14, 24, 22};        
        getSubSetSums(arr, sums);

    }
}
于 2014-02-21T04:24:40.023 に答える