Задача на комбинаторику

Leonid · 6 Сен 2010

Задача на комбинаторику

Задача такая. На турсайте в 2-х столбцах выводятся спецпредложения по разным странам. стран около 10, по каждой может быть от 1 до ~100 спецпредложений.

Если выводить поочередно, например в левый столбец 1, 3, 5 и т.д. страны, в левый 2, 4, 6, то может получиться так, что в одном столбце контента в 2 - 3 раза больше.

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

В общем задача сводится к такому:

есть массив из N элементов (5 - 12). Каждый элемент имеет какое-то значение. Нужно разделить массив на 2 группы, чтобы в обоих было примерно одинаковые суммы значений.

Например массив
[1] => 20
[2] => 10
[3] => 3
[4] = >16
[5] => 30
[6] => 40

будет разделен так:
[1] + [2] + [5] => 20 + 10 + 30 = 60
[6] + [4] + [3] => 40 + 16 + 3 = 59

а массив
[1] => 2
[2] => 3
[3] => 4
[4] = >7
[5] => 1
[6] => 40

будет разделен так:
[1] + [2] + [3] + [4] + [5] => 2 + 3 + 4 + 7 + 1 = 17
[6] => 40

zerkms · 6 Сен 2010

Решение в лоб:

По очереди выкладывать в "нужную" кучку

PHP:

$arr = array(2,3,4,7,1,40);

rsort($arr);

$stack1 = $stack2 = 0;

foreach ($arr as $val)
{
	if ($stack1 <= $stack2)
	{
		$stack1 += $val;
	}
	else
	{
		$stack2 += $val;
	}
}

var_dump($stack1, $stack2);

tenshi · 6 Сен 2010

Задача об упаковке в контейнеры np-полная %-)

zerkms · 6 Сен 2010

tenshi
Эту задачу можно подвести под классическую задачу о рюкзаке?

UPD: даже если можно (в чём я немного сомневаюсь), то - зачем?

ХакИрФсимагущий · 6 Сен 2010

Все гениальное просто))
Сначало сортируем по убыванию
потом сравнимвем сначлало 1 элемент с 6ю потом 2 с 5, 3 с 4
потом как только выяснилось что 3(предложения) больше 4(предложений)( Примерно это было продемонстрированно zerkms) на 33 то идем обратно и сравниваем.
а дальше проверяем
На сколько 2 меньше 5, обробатываем данныеи выводим ответ.

partizan · 7 Сен 2010

Автор оригинала: zerkms
tenshi
Эту задачу можно подвести под классическую задачу о рюкзаке?

UPD: даже если можно (в чём я немного сомневаюсь), то - зачем?

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

zerkms · 7 Сен 2010

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

-~{}~ 07.09.10 09:25:

Если я правильно понял, что автору нужно минимизировать разницу между кол-вом ел-тов в левой и правой колонках.

неправильно ты понял.

Нужно разделить массив на 2 группы, чтобы в обоих было примерно одинаковые суммы значений.

partizan · 7 Сен 2010

Re: Задача на комбинаторику

А я что написал?

Автор оригинала: Leonid
разделить массив на 2 группы, чтобы в обоих было примерно одинаковые суммы значений.

Автор оригинала: partizan
минимизировать разницу

zerkms · 7 Сен 2010

минимизировать разницу между кол-вом ел-тов

ты свои же слова прочесть не можешь?

partizan · 7 Сен 2010

Под "кол-вом ел-тов" я имел ввиду кол-во спецпредложений в стране

zerkms · 7 Сен 2010

Ладно, пусть будет так. Решите эту задачу с помощью алгоритмов решения задачи рюкзака. И сделайте это проще, чем это сделано в моём ответе.

partizan · 7 Сен 2010

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

$arr = array(2,3,4,7,1,40,100);

Получим:

2 4 1 40
3 7 100

Тогда как оптимальное разбиение:
2,3,4,7,1,40
100

zerkms · 7 Сен 2010

Получим:

нет, не получим. можешь убедиться сам, выполнив код.

WBS · 7 Сен 2010

PHP:

<?

$arr = array(25,25,20,30,40);
// $arr = array(20,10,3,16,30,40);
// $arr = array(2,3,4,7,1,40);
$arr_size = sizeof($arr);
$min_i = pow(2,$arr_size);
$max_i = 1.5*$min_i;

$min_diff_val = $min_diff_bin = NULL;
for ($i=$min_i; $i<$max_i; $i++) {
	$bin = decbin($i);
	$stack1 = $stack2 = 0;
	for ($j=0; $j<$arr_size; $j++)
		substr($bin, $j+1, 1) ? $stack1 += $arr[$j] : $stack2 += $arr[$j];
	$diff = abs($stack1-$stack2);
	if ($min_diff_val===NULL || $min_diff_val > $diff) {
		$min_diff_val = $diff;
		$min_diff_bin = $bin;
	}
	if ($min_diff_val==0)
		break;
}

$stack1_arr = $stack2_arr = array();
for ($j=0; $j<$arr_size; $j++)
	substr($min_diff_bin, $j+1, 1) ? $stack1_arr[] = $arr[$j] : $stack2_arr[] = $arr[$j];

print("<b>Array:</b><br>".implode($arr,", ")."<p><b>Stack 1:</b><br>".implode($stack1_arr,", ")."<p><b>Stack 2:</b><br>".implode($stack2_arr,", "));

?>

partizan · 7 Сен 2010

Автор оригинала: zerkms
нет, не получим. можешь убедиться сам, выполнив код.

Был не прав, не заметил, что сортировка по убыванию там. Но всеравно есть контр-пример:

$arr = array(10, 9, 8, 6, 5, 1);

Получим:

10+6+5 = 21
9+8+1 = 18

А можно было разделить так:
8+6+5 = 19
9 + 10 + 1 = 20

-~{}~ 07.09.10 04:06:

Кстати, код от WBS для приведенного примера дает правильный ответ, хотя и не пойму, как он работает

Leonid · 7 Сен 2010

Я решил задачу несколько по-иному, но вроде работает. Смысл в том, что сначала сортирую массив по убыванию:

[6] => 40
[4] = >7
[3] => 4
[2] => 3
[1] => 2
[5] => 1

а потом уже своим вторым способом. Т.е.
беру первое значение (40) и в левый столбец. Потом следующее значение в тот столбец, в котором в данный момент элементов меньше, т.е. в правый. Следующий элемент также.

rotoZOOM · 7 Сен 2010

Leonid как уже говорили ранее, жадный алгоритм в данном случае далеко не всегда выдает верное решение.
10
9
8
8
3

CHEM_Eugene · 7 Сен 2010

Поделюсь своим вариантом решения. Основывался на решении задачи о дележе

PHP:

<?php
function delej($array)
{
	// Массив результатов
	$result[1] = array();
	$result[2] = array();
	
	// Количество записей	
	$num = 	sizeof($array);
	// Оценки первой группы
	$values1 = generate(0, 100, 100, $num);
	// Оценки второй группы
	$values2 = generate(0, 100, 100, $num);
	
	// Первичная раздача
	for ($i=0; $i<$num; $i++)
	{
		if ($values1[$i] > $values2[$i])
		{
			$result[1][] = $array[$i]; 
		} else if ($values2[$i] > $values1[$i])
		{
			$result[2][] = $array[$i];
		} else
		{
			// отдаем тому, у кого меньше
			$k = (array_sum($result[1]) < array_sum($result[2]))? 1 : 2;
			$result[$k][] = $array[$i];
		}
	}
	
	// Корректировка
	return correct($result);
}

function generate($min, $max, $sum, $num)
{
	$result = array();
	
	for ($i=0; $i<$num; $i++)
	{
		switch ($i)
		{
			case 0:
				$result[$i] = rand($min, $max);
			break;
			
			case $num-1:
				$result[$i] = $sum - array_sum($result);
			break;
			
			default:
				$result[$i] = rand($min, $sum - array_sum($result));
			break;
		}
	}
	
	return $result;
}

function correct($array)
{
	$k_max = (array_sum($array[1]) < array_sum($array[2]))? 2 : 1;
	
	sort($array[$k_max]);
	$min_el = array_shift($array[$k_max]);
	$k_min = ($k_max == 2)? 1 : 2;

	$array[$k_min][] = $min_el;
	
	$k_max = (array_sum($array[1]) < array_sum($array[2]))? 2 : 1;
	$k_min = ($k_max == 2)? 1 : 2;
	if (array_sum($array[$k_max])/array_sum($array[$k_min]) > 1.4)
	{
		if (sizeof($array[$k_max]) == 1) 
		{
			echo "Невозможно поделить поровну\n";
			return $array;			
		}
		return correct($array);
	} else
	{
		echo "SUM_MAX: ".array_sum($array[$k_max])."\n"; 
		echo "SUM_MIN: ".array_sum($array[$k_min])."\n";
		return $array;
	}
	
}

$test = Array(20, 10, 3, 16, 30, 40);
$result = delej($test);
var_dump($result);
?>

Если кому надо, опишу суть метода (если из кода не понятно).

rotoZOOM · 8 Сен 2010

Какие еще рандомы?? Есть вполне конкретное четкое решение, которое при любых исходных данных дает наилучший результат.
Сложность O(n*2^n), у ТС максимум 12 элементов, значит итераций будет около 50000 это не так много.

PHP:

function getArrangement ($arr)
{
	$sz = count($arr);
	$num = 1<<$sz;
	$best = 1000000000;
	for ($i = 1 ; $i < $num ; $i++)
	{
		$s=array(0,0);
		for ($j=0 ; $j < $sz ; $j++)
		{
			$s[($i & (1<<$j)) != 0] += $arr[$j];
		}
		if (abs($s[0]-$s[1]) < $best)
		{
			$best = abs($s[0]-$s[1]);
			$besti = $i;
		}
	}

	/// нашли расстановку, собираем два массива
	$res = array (array(),array());
	for ($j=0 ; $j < $sz ; $j++)
	{
		$res[($besti & (1<<$j)) != 0][] = $arr[$j];
	}
	return $res;
}

var_dump (getArrangement (array(10,9,8,8,3)));

-~{}~ 08.09.10 09:05:

CHEM_Eugene решение у тебя некорректное.

CHEM_Eugene · 8 Сен 2010

rotoZOOM, оно вполне корректное. Метод приближенный, а не точный, поэтому глобальный максимум может быть и не найден, но можно немного модифицировать алгоритм и он будет искать наилучшее решение.

Задача на комбинаторику

PHP? нет, не слышал...

TDD infected

Новичок

TDD infected

[засикречино]

Новичок

TDD infected

Новичок

TDD infected

Новичок

TDD infected

Новичок

TDD infected

Новичок

Новичок

PHP? нет, не слышал...

ACM maniac

Новичок

ACM maniac

Новичок