Алгоритм: извлечение подмножества на основе суммы имущества

Ответ 1

Это похоже на 0-1 Проблема с рюкзаком или Задача суммы подмножества.

Если веса не являются очень большими целыми числами, решение динамического программирования должно быть эффективным.

Вот реализация алгоритма динамического программирования javascript. Если вы хотите случайные группы, просто произвольно перетасовывайте список людей перед применением этого алгоритма.

var p = {
   jane:126,
   julia:112,
...
};

function subset(people, min, max)
{
  var subsets = [];
  subsets[0] = '';

  for (var person in people)
  {
    for (var s = min-1; s >= 0; --s)
    {
      if (s in subsets)
      {
        var sum = s + people[person];

        if (!(sum in subsets))
        {
          subsets[sum] = subsets[s] + ' ' + person;

          if (sum >= min && sum <= max)
          {
            return subsets[sum];
          }
        }
      }
    }
  }

  return 'Not found';
}

print(subset(p, 818, 822));

Ответ 2

Похоже на вариант "проблемы с двоичным рюкзаком" с добавленной оценкой, что если наилучшее соответствие по-прежнему находится за пределами допустимого диапазона, ответ отклоняется.

Вы можете захотеть взглянуть на "полиномиальные приближения времени".

Одним из подходов может быть сортировка по весу. Затем вы начинаете смотреть с середины вниз и вверх: вы получаете дан, джон, давид, алекс, а вы в 779. Вы добавляете Джейн и оказываетесь в 905, и это слишком много на 87; поэтому вы проверяете имя ниже, julia, это 112, и посмотрите ближайший матч между различиями. Обмен Алекса с Джулией (210-112) потеряет вас 98, обмен Дэвидом с Джулией потеряет 84. Скорее, промойте, повторите.

Алгоритм O (n log n) для сортировки, а затем зависит от заданного размера. У этого есть несколько недостатков (не гарантируется схождение, группы будут иметь тенденцию быть смежными, они собирают людей вблизи начальной точки и т.д.), Но если вы просто хотите "группу", этого может быть достаточно.

Вы также можете реализовать алгоритм рекурсивно. Самый худший случай был бы O (n ^ 3 log n), но если вы действительно работаете с людьми (веса, сгруппированные в разумно малые диапазоны, плавная кривая), конвергенция, вероятно, будет довольно быстрой.

Ответ 3

Это то, что я называю проблемой "сортировка и скобка". Способ, которым вы его решаете, заключается в сортировке данных, а затем в брекетинге вокруг целевого значения или целевого диапазона.

Например, в этом случае отсортированный порядок:

98
112
126
182
191
196
210
213
223
237

Теперь вы усредняете список: 178.8. Поэтому стартовый кронштейн равен (126,182). Начните перемещаться из этого среднего: сумма (126,182,112,191,98) = 709, слишком мала. Удалите 98 и замените значение с другой стороны: 196, т.е. Сумма (126,182,112,191,196) = 807, все еще слишком малая. Перейдите к следующему значению с высокой стороны, сумме (126,182,112,191,210) = 821. Хорошо, нашел одно совпадение. Продолжая этот процесс, вы можете найти каждый матч. В основном, что брекетинг помогает вам искать только подмножество всех возможных комбинаций, поэтому вам не нужно проверять каждую комбинацию. Вы генерируете комбинации наружу от среднего, а не от одного или другого.

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

Метод реализации: для реализации этого алгоритма вам необходимо создать генератор комбинаций, который работает в "лексикографическом" порядке. Затем вы начинаете с n, например 5, пунктов и определяете медианную комбинацию, как я показал выше. Затем вы получаете следующую более низкую комбинацию, если вы новичок, вы переключаетесь на следующую более высокую комбинацию и так далее.

-------------- ДОБАВЛЕНИЕ -------------------

Подумав об этом, может быть лучше использовать простой алгоритм изменения типа, а не лексикографический комбинатор. Этот тип алгоритма генерирует все комбинации, но только переключает любые 2 элемента в данный момент времени. В основном вы изменяете этот алгоритм для переключения направления, когда он выходит за пределы (выходит за пределы диапазона или ниже).

Ответ 4

Вот ответ на аналогичный вопрос Найти комбинацию суммы элементов (элементов) в массиве, сумма которых равна заданному числу

<?php

$limit = 12;
$array = array(6,1,10,4,1,3,11,2,15,5,12,10,17);

echo implode(', ',$array).'<br>';

// remove items 15 and 17 because they are great then $limit = 12
$array = array_filter($array, function($var) use ($limit) {
  return ($var <= $limit);
});

rsort($array);
echo implode(', ',$array);

// the algorithm is usable if the number of elements is less than 20 (because set_time_limit)
$num = count($array); 

//The total number of possible combinations 
$total = pow(2, $num);

$out = array();

// algorithm from http://r.je/php-find-every-combination.html
// loop through each possible combination  
for ($i = 0; $i < $total; $i++) {  

    $comb = array();

    // for each combination check if each bit is set 
    for ($j = 0; $j < $num; $j++) { 
       // is bit $j set in $i? 
        if (pow(2, $j) & $i){
          $comb[] = $array[$j];
        }      
    } 

    if (array_sum($comb) == $limit)
    {
      $out[] = $comb;
    }
}

array_multisort(array_map('count', $out), SORT_ASC, $out);

$out = array_unique($out, SORT_REGULAR);

foreach($out as $result) echo implode(', ', $result).'<br>';

Результатом этого кода является список комбинаций, сумма которых равна $limit (12)...

12
10, 2
11, 1
5, 4, 3
6, 4, 2
6, 5, 1
10, 1, 1
5, 4, 2, 1
6, 3, 2, 1
6, 4, 1, 1
5, 3, 2, 1, 1