Наиболее понятным образом принцип работы
Наиболее понятным образом принцип работы нашей программы можно продемонстрировать на примере.
| Вес | 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 |
2
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 2 |
| dif | 38 | 13 | 13 | 13 | 3 |
3
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 1 |
| dif | 38 | 13 | 13 | 0 | 8 |
4
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 1 | 0 | 0 | 0 |
| dif | 38 | 13 | 13 | 13 | 13 |
5
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 1 | 1 |
| dif | 38 | 38 | 16 | 7 | 2 |
6
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 1 | 0 |
| dif | 38 | 38 | 16 | 7 | 7 |
7
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 2 | 0 | 2 |
| dif | 38 | 38 | 16 | 16 | 6 |
10
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 1 | 2 | 1 |
| dif | 38 | 38 | 27 | 9 | 4 |
12
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 1 | 1 | 2 |
| dif | 38 | 38 | 27 | 18 | 8 |
17
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 2 | 2 |
| dif | 38 | 38 | 38 | 20 | 10 |
22
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 0 | 2 |
| dif | 38 | 38 | 38 | 38 | 28 |
24
| ves | - | 25 | 11 | 9 | 5 |
| take | 0 | 0 | 0 | 0 | 0 |
| dif | 38 | 38 | 38 | 38 | 38 |
Итак, мы убедились в том, что найденное в самом начале значение переменной razn и было минимальным (найденные группы весов соответственно 25 + 11 = 36 и 11 + 9 + 9 + 5 + 5 = 39). Необходимо отметить, что из приведенных выше таблиц видно (см. шаг 5), что существует еще один способ разделить приведенный набор весов таким же оптимальным образом: (11 + 11 + 9 + 5 = 36 и 25 + 9 + 5 = 39). Найденная разница 39 - 36 = 3 и будет окончательным результатом, который программа сообщит пользователю.
