Лабораторная работа 65

Дано N предметов разного веса. Разложить их в две группы так, чтобы общие веса двух групп были максимально близки.

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

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

Type Dat = record
         C, D : Integer;
     End;

Где С и D - вес и группа, к которой относится предмет, соответственно. Массив возьмём нарочно большой, чтобы можно было записать много чисел. Хотя можно использовать и списки.

Var M : Array [1..100] Of Dat;

Так как мы ищем разность между весами, то группы будем обозначать числами +1 и -1. Так найти разность будет проще. Достаточно будет сложить произведения веса и группы предметов. Кстати, группа со значением 0 будет означать, что этот предмет ещё не разложен в какую-либо группу, и такое произведение на общий баланс не повлияет.

Функция, которая находи баланс приведена ниже:

Function Balans:Integer;
Var Result : Integer;
    I : Integer;
Begin
     Result := 0;
     I := 1;
     While M[I].D <> 0 Do
     Begin
          Result := Result + M[I].C * M[I].D;
          Inc(I);
     End;
     Balans := Result;
End;

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

Теперь можно приступать к самому распределению.

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

I := 1;
While M[I].C <> 0 Do
Begin
	If Balans < 0
	Then M[I].D := 1
	Else M[I].D := -1;
	Inc(I);
End;

Кстати, это метод намного быстрее, чем полный перебор всех вариантов, хотя, и такой способ имеет право на существование.

Пахтусов Сергей, 14.07.2006