сопоставлять элементы со списком сумм

Question

Если у меня есть массив чисел и список сумм, суммирующих элементы массива, то какой наиболее эффективный подход (или, по крайней мере, не грубой взлом) для определения того, какой из элементов включены в сумму?

Упрощенный пример может выглядеть следующим образом:

массива = [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/

Я знаю, что всегда будет по крайней мере один правильный ответ, и это только для меня важно, что номера проверить, не нужно спариваться индекс, где есть дубликаты, только поскольку это относится к сумме. Существует ли установленная функция для решения этой проблемы?

Это только javascript-вопрос, потому что это язык, на котором я пишу решение, это скорее общий вопрос, связанный с математикой, который фильтруется через Javascript. Если это не подходящий форум, я приветствую перенаправление на соответствующий сайт обмена стеками.

Answer 1

Ok , проклинаю меня, это мой нокаут, улучшения приветствуются :)

Я считаю, что это Bin Packing Problem или knapsack problem

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

Answer 2

Проблема подмножестве суммы является 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); 

    } 
} 

Answer 3

Возможно, было бы поучительно показать, как это можно закодировать в системе программирования ограничений (здесь 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]; 

Матрица «х» интересная часть, х [I, J] = 1 (истина), если число «НУМС [J]» используется в сумме число «суммы [i]».

Для этой конкретной проблемы есть 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] 
---------- 
... 

Они являются не отдельными решениями, так как есть два 6-х. С помощью всего лишь один 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} 

И наоборот, максимальное количество чисел, используемых (здесь все номера используются с 6 подсчитывают только один раз в «с»):

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, как в этой проблеме совпадения.)