Расчет ограниченного декартова произведения-PHP

Прошу прощения, но это будет скорее логическая схема, чем код...

Мне не совсем ясно, является ли массив (1,2,3,4) баллами для первого блюда или для первого повара, но я бы, вероятно, использовал такой массив, что

$array[$cook_id][$dish_number] = $score;

Asort () каждый массив так, что $array[$cook_id] = array($lowest_scored_dish,..., $highest);

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

Как очень простой пример, повара a, b, c и блюда 0,1,2

$array['a'] = array(0=>100, 1=>50, 2=>0); // cook a prefers 0 over 1 with weight 50, over 2 with weight 100
$array['b'] = array(0=>100, 1=>100, 2=>50); // cook b prefers 0,1 over 2 with weight 50
$array['c'] = array(0=>50, 1=>50, 2=>100); // cook c prefers 2 with weight 50

После асорта(): $array ['a'] = массив(0=>100, 1=>50, 2=>0); $array ['b'] = массив(0=>100, 1=>100, 2=>50); $array ['c'] = массив(2=>100, 0=>50, 1=>50);

Начните с повара "А", который предпочитает блюдо 0 своему следующему лучшему блюду на 50 баллов (вес). Повар ' b ' также предпочитает dih 0, но с весом 0 над следующим блюдом. Поэтому вполне вероятно (хотя еще не уверен, что повар " а " должен приготовить блюдо 0.

Считайте блюдо 0 зарезервированным и переходите к приготовлению 'b'. Исключая блюдо 0, повар " б " предпочитает блюдо 1. Ни один другой повар не предпочитает блюдо 1, поэтому повару " б " назначается блюдо 1.

Cook ' c ' получает блюдо 2 по умолчанию.

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

Давайте сделаем это менее удобным:

$array['a'] = array(0=>75, 1=>50, 2=>0);
$array['b'] = array(0=>100, 1=>50, 2=>50);
$array['c'] = array(0=>100, 1=>25, 2=>25);

Начните снова с cook 'a' и убедитесь, что 0-это предпочтительнее, но на этот раз с весом 25. Повар " б "предпочитает с весом 50, а повар" с " предпочитает с весом 75. Повар ' c ' выигрывает блюдо 0.

Возвращаясь к списку доступных поваров, " а "предпочитает 1 с весом 50, но" б " предпочитает его с весом 0. "а" получает блюдо 1, А " Б " - блюдо 2. Это все еще не решает всех сложностей, но это шаг в правильном направлении. Иногда предположение, сделанное для первой комбинации повар / блюдо, будет неверным.

Путь менее удобно:

$array['a'] = array(0=>200, 1=>148, 2=>148, 3=>0);
$array['b'] = array(0=>200, 1=>149, 2=>0, 3=>0);
$array['c'] = array(0=>200, 1=>150, 2=>147, 3=>147);
$array['d'] = array(0=>69, 1=>18, 2=>16, 3=>15);

'a' получает 0, так как это максимум, и никто другой, кто предпочитает 0, не имеет большего веса "б" выигрывает 1 с весом 149 'd' выигрывает 2, так как 'c' не имеет предпочтения из доступных вариантов 'c' получает 3

Оценка: 200+149+147+16 = 512

Хотя это хорошая догадка, собранная без проверки каждой перестановки, она может быть неправильной. Отсюда спросите :" если бы один повар торговал с любым другим поваром, общая сумма увеличилась бы?"

Ответ-да., a (0)+d(2) = 200+16 = 216, но a (2)+d(0) = 148+69 = 217.

Я оставляю вам написать код для "лучшего предположения", используя взвешенный подход, но после этого, вот хорошее начало для вас:

// a totally uneducated guess...
$picks = array(0=>'a', 1=>'b', 2=>'c', 3=>'d');

do {
    $best_change = false;
    $best_change_weight = 0;
    foreach ($picks as $dish1 => $cook1) {
        foreach ($picks as $dish2 => $cook2) {
            if (($array[$cook1][$dish1] + $array[$cook2][$dish2]) <
                ($array[$cook1][$dish2] + $array[$cook2][$dish1]))
            {
                $old_score = $array[$cook1][$dish1] + $array[$cook2][$dish2];
                $new_score = $array[$cook1][$dish2] + $array[$cook2][$dish1];
                if (($new_score - $old_score) > $best_change_weight) {
                    $best_change_weight = $new_score - $old_score;
                    $best_change = $dish2;
                }
            }
        }
        if ($best_change !== false) {
            $cook2 = $picks[$best_change];
            $picks[$dish1] = $cook2;
            $picks[$dish2] = $cook1;
            break;
        }
    }
} while ($best_change !== false);

Я не могу найти встречного примера, чтобы показать, что это не работает, но я с подозрением отношусь к тому случаю, когда ($array[$cook1][$dish1] + $ array[$cook2][$dish2]) == ($array[$cook1][$dish2] + $ array[$cook2][$dish1])

Может быть, кто-то еще последует с ответом на это "а что, если?"

Дана эта матрица, где пункты в скобках являются "выборками"

[a1]   a2   a3
 b1   [b2]  b3
 c1    c2  [c3]

Если a1 + b2 == a2 + b1, то' a 'и' b ' не будут переключать тарелки. Случай, в котором я не уверен на 100%, если существует матрица, такая что это лучший выбор:

 a1   [a2]   a3
 b1    b2   [b3]
[c1]   c2    c3

Переход из первого состояния во второе требует двух переключателей, первый из которых кажется произвольным, так как он не изменяет общую сумму. Но, только пройдя через это произвольное изменение, последний переключатель может быть сделал. Я попытался найти пример 3x3 такой, что на основе модели "взвешенного предпочтения", о которой я писал выше, будет выбран первый, но также и такой, что реальный оптимальный выбор задается вторым. Я не смог найти пример, но это не значит, что его не существует. Сейчас мне не хочется заниматься матричными алгебрами, но, может быть, кто-нибудь продолжит с того места, где я остановился. Черт возьми, может быть, этого дела и не существует, но я подумал, что должен указать на беспокойство.

Если это действительно работает, и вы начинаете с правильного выбора, приведенный выше код будет только цикл через 64 раза (8x8) для 8 поваров/блюд. Если выбор не правильный и первый повар имеет изменение, то он будет идти до 72. Если у 8-го повара есть сдача, это до 128. Возможно, что do-while будет циклически повторяться несколько раз, но я сомневаюсь, что он встанет рядом с циклами процессора, необходимыми для суммирования всех комбинаций 40k.

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

$cooks = array(
    array(1,2,3,4),
    array(35,0,0,0),
    array(36,33,1,1),
    array(20,20,5,3)
);
$results = array();

while (count($cooks)) {
    $curResult = array(
        'cookId' => -1,
        'recipe' => -1,
        'score'  => -1,
        'ratio'  => -1
    );
    foreach ($cooks as $cookId => $scores) {
        $max = max($scores);
        $ratio = $max / array_sum($scores);
        if ($ratio > $curResult['ratio']) {
            $curResult['cookId'] = $cookId;
            $curResult['ratio']  = $ratio;
            foreach ($scores as $recipe => $score) {
                if ($score == $max) {
                    $curResult['recipe'] = $recipe;
                    $curResult['score']  = $score;
                }
            }
        }
    }

    $results[$curResult['recipe']] = $curResult['score'];
    unset($cooks[$curResult['cookId']]);
    foreach ($cooks as &$cook) {
        unset($cook[$curResult['recipe']]);
    }
}

Для предоставленного набора данных он находит то, что кажется оптимальным ответом (35,33,5,4). Однако он все еще не совершенен, например, с массивом:

$cooks = array(
    array(1,2,3,4),
    array(35,0,33,0),
    array(36,33,1,1),
    array(20,20,5,3)
);

Идеальным ответом было бы (20,33,33,4), однако это алгоритм вернет (35,33,5,4).

Но поскольку вопрос требовал идей о том, с чего начать, я думаю, что этого, по крайней мере, может быть достаточно, чтобы начать с чего-то: P

Попробуйте это

$mainArr = array(
   array (1,2,3,4) ,
   array (35,0,0,0) ,
   array (36,33,1,1) ,
   array (20,20,5,3) 
 );
$i = 0;
foreach( $mainArr as $subArray )
{
    foreach( $subArray as $key => $value)
    {
        $newArr[$key][$i]=$value;
        $i++;   
    }
}
$finalArr = array();
foreach( $newArr as $newSubArray )
{
    $finalArr[] = max($newSubArray);    
}
print_r( $finalArr );