Не могу найти оптимальный алгоритм

VHS, на чем хоть пишите?) Думаю нужно сделать отдельный класс Unit, в нем будет содержаться ваше значение сколько использовано и флаг (boolean) можно ли его использовать снова. Если флаг true то используете и делаете его false.

Да без разницы, алгоритм это алгоритм, без привязки к языку

---------- Добавлено 23.05.2015 в 17:07 ----------

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

$unit[0] = 100; // использовано целое изделие
$unit[1] = 15; // остаток 85
$unit[2] = 19; // остаток 81
$unit[3] = 63; 
$unit[4] = 43;
$unit[5] = 35; 
$unit[6] = 84;
$unit[7] = 22;

$percents = array();
$total_units = 0;

foreach ($unit as $key => $value) {
	if ($value >= 100) {
		$total_units++;
		unset($unit[$key]);
		$percents[] = 100;
	}
}

if (count($unit)) {
	rsort($unit);
	foreach ($unit as $key => $value) {
		if (!isset($unit[$key])) {
			continue;
		}
		unset($unit[$key]);
		$ok = false;
		foreach ($unit as $key2 => $value2) {
			if ($value + $value2 > 100) {
				continue;
			} else {
				$ok = true;
				$total_units++;
				unset($unit[$key2]);
				$percents[] = $value.' + '.$value2.' = '.($value + $value2);
				break;
			}
		}
		if (!$ok) {
			$total_units++;
			$percents[] = $value;
		}
	}
}

echo implode('<br>', $percents);
echo '<br>Total: '.$total_units.' units';

Тогда думаю надо 2 списка, 1 с единицами товара, 2 с остатками. При использовании единицы, создаем объект "остаток" и лежим его с список. Потом при использовании 2-й единицы, сортируем список с остатками от наименьшего до наибольшего и проходим по списку находим то, что нам подходит (если есть), используем и удаляем из списка. Если не нашли, то оставляем для следующей единицы, а сами берем новую деталь.

Еще если изначально вы знаете сколько на каждую деталь надо материала, то можно тоже отсортировать и начать с наименьшей.

Навверно, так. Отсортировать массив. Если элементов не очень много, то перебирать таким образом, чтобы сумма слагаемых равнялась одному из элементов массива.

Надо как-то продумать, каким образом это сделал бы человек.

LovelAss, спасибо, пока не вижу изъяна, активно тестирую. В любом случае это лучше, чем было у меня.

anser06, проблема в том, что среднестатистический человек не в состоянии это сделать, т.к. количество обрезков в среднем около 40шт, в зависимости от площади покрытия сильно не меняется.

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

Спасибо за ссылку.

Однако тут вариант несколько иной, полный перебор всех вариантов не требуется, и метод LovelAss действительно при всех испробованных мною вариантах обрезков выдал оптимальный результат.

Для тех кто не понял что происходит:

1 - сортируем массив по значению

2 - начинаем перебор элементов в цикле

3 - если изделие целое (условно равное 100) - удаляем его из массива, увеличиваем счетчик

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

5 - в итоге остаются только части такого размера, что из 1 целого изделия получить два куска нельзя.

Профит. - кликабельно, массив генериться рандомно при обновлении

P.S. на самом деле нужен был алгоритм, т.к. изделия режутся и вдоль и поперек, т.е. схема куда сложнее, но это уже другая история.

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

Долго вспоминал чему учился в институте. Никак не мог вспомнить что же это за метод :)