Наиболее понятным образом принцип работы

Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.

Вес	25	11	9	5
Количество	1	2	2	2

Пусть имеется семь предметов (n = 7) с весами 9, 5, 25, 11, 9, 5, и 11 единиц (килограмм, фунтов, бушелей...). Тогда всего есть четыре разных вида предметов (k = 4).
Общая сумма весов равна 75; следовательно, "большая половина" sum = 38. Теперь нужно найти такой набор предметов, чей суммарный вес будет наиболее близким к этой "золотой середине". Кроме того, не стоит забывать и о сделанном ранее замечании: как только найдется набор, вес которого отличается от "золотого" лишь на единицу, поиск можно закончить.
Начнем теперь заполнять массивы take и dif (массив dif хранит остатки, в пределах которых можно проводить дальнейшие вычисления).
На начальном ("нулевом") шаге мы заполним массив take так, чтобы в создаваемый набор попали по возможности самые тяжелые предметы (см. раздел реализации "Основная часть программы"). Таким образом, получим следующие состояния массивов:

ves	-	25	11	9	5
take	0	1	1	0	0
dif	38	13	2	0	0

После этого шага переменная razn, которая хранит отклонение текущего набора весов от оптимального, будет содержать значение 2. Попытаемся уменьшить это значение (переход к разделу реализации "Заполнение массива").
Двигаясь от конца массива take к его началу, будем уменьшать поочередно каждую его ненулевую компоненту. Разумеется, при этом будут возникать изменения в хвосте этого массива; эти изменения мы будем вносить туда в обычной последовательности "от начала к концу".
Таким образом, наши массивы последовательно примут следующие значения (некоторые непринципиальные шаги опущены):
1

ves	-	25	11	9	5
take	0	1	0	1	0
dif	38	13	13	4	0

ves	-	25	11	9	5
take	0	1	0	0	2
dif	38	13	13	13	3

ves	-	25	11	9	5
take	0	1	0	0	1
dif	38	13	13	0	8

ves	-	25	11	9	5
take	0	1	0	0	0
dif	38	13	13	13	13

ves	-	25	11	9	5
take	0	0	2	1	1
dif	38	38	16	7	2

ves	-	25	11	9	5
take	0	0	2	1	0
dif	38	38	16	7	7

Содержание Назад Вперед