Уравнение ранца с группами предметов

Ответ 1

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

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

def all_subsets(S):  # brute force
    subsets_so_far = [()]
    for x in S:
        new_subsets = [subset + (x,) for subset in subsets_so_far]
        subsets_so_far.extend(new_subsets)
    return subsets_so_far

Тогда есть функция, которая возвращает True, если решение действительно (в пределах бюджета и с правильным разбиением позиции) - вызовите его is_valid_solution - и функцию, которая при решении возвращает общее значение игрока (total_player_value). Предполагая, что players - список доступных игроков, оптимальным решением является это.

max(filter(is_valid_solution, all_subsets(players)), key=total_player_value)

Теперь для DP добавим функцию cull в all_subsets.

def best_subsets(S):  # DP
    subsets_so_far = [()]
    for x in S:
        new_subsets = [subset + (x,) for subset in subsets_so_far]
        subsets_so_far.extend(new_subsets)
        subsets_so_far = cull(subsets_so_far)  ### This is new.
    return subsets_so_far

Что cull заключается в том, чтобы отбросить частичные решения, которые, очевидно, не будут упущены в нашем поиске оптимального решения. Если частичное решение уже превышает бюджет, или если у него уже слишком много игроков в одной позиции, тогда его можно безопасно отбросить. Пусть is_valid_partial_solution - функция, проверяющая эти условия (она, вероятно, очень похожа на is_valid_solution). Пока у нас это есть.

def cull(subsets):  # INCOMPLETE!
    return filter(is_valid_partial_solution, subsets)

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

def cull(subsets):
    best_subset = {}  # empty dictionary/map
    for subset in filter(is_valid_partial_solution, subsets):
        key = cost_and_position_breakdown(subset)
        if (key not in best_subset or
            total_value(subset) > total_value(best_subset[key])):
            best_subset[key] = subset
    return best_subset.values()

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

Ответ 2

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

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

function make_teams($players, $position_limits, $weights, $values, $max_weight){
  $player_counts = array_map(function($x){
                     return count($x);
                   }, $players);
  $positions = array_map(function($x){ 
                 $positions[] = []; 
               },$position_limits);
  $num_positions = count($positions);
  $combinations = [];
  $hash = [];
  $stack = [[$positions,0,0,0,0,0]];

  while (!empty($stack)){
    $params = array_pop($stack);
    $positions = $params[0];
    $i = $params[1];
    $j = $params[2];
    $len = $params[3];
    $weight = $params[4];
    $value = $params[5];

    // too heavy
    if ($weight > $max_weight){
      continue;

    // the variable, $positions, is accumulating so you can access the partial result
    } else if ($j == 0 && $i > 0){

      // remember weight and value after each position is chosen
      if (!isset($hash[$i])){
        $hash[$i] = [$weight,$value];

      // end thread if current value is lower for similar weight
      } else if ($weight >= $hash[$i][0] && $value < $hash[$i][1]){
        continue;

      // remember better weight and value
      } else if ($weight <= $hash[$i][0] && $value > $hash[$i][1]){
        $hash[$i] = [$weight,$value];
      }
    }

    // all positions have been filled
    if ($i == $num_positions){
      $positions[] = $weight;
      $positions[] = $value;

      if (!empty($combinations)){
        $last = &$combinations[count($combinations) - 1];
        if ($weight < $last[$num_positions] && $value > $last[$num_positions + 1]){
          $last = $positions;
        } else {
          $combinations[] = $positions;
        }
      } else {
        $combinations[] = $positions;
      }

    // current position is filled
    } else if (count($positions[$i]) == $position_limits[$i]){
      $stack[] = [$positions,$i + 1,0,$len,$weight,$value];

    // otherwise create two new threads: one with player $j added to
    // position $i, the other thread skipping player $j
    } else {
      if ($j < $player_counts[$i] - 1){
        $stack[] = [$positions,$i,$j + 1,$len,$weight,$value];
      }
      if ($j < $player_counts[$i]){
        $positions[$i][] = $players[$i][$j];
        $stack[] = [$positions,$i,$j + 1,$len + 1
                   ,$weight + $weights[$i][$j],$value + $values[$i][$j]];
      }
    }
  }
  return $combinations;
}

Вывод:

$players = [[1,2],[3,4,5],[6,7]];
$position_limits = [1,2,1];
$weights = [[2000000,1000000],[10000000,1000500,12000000],[5000000,1234567]];
$values = [[33,5],[78,23,10],[11,101]];
$max_weight = 20000000;

echo json_encode(make_teams($players, $position_limits, $weights, $values, $max_weight));

/*
[[[1],[3,4],[7],14235067,235],[[2],[3,4],[7],13235067,207]]
*/