Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

Листинг 3.14. Оптимальный выбор 
void Opt(int i, int weight, int cost) 
{ 
if (weight + a[i].weight <= maxWeight) 
{ 
s |= (1 << i); // s=s+[i]; 
добавление в выборку 
if (i < n-1) 
Opt(i+1, weight+a[i].weight, cost); 
else 
if (cost > maxCost) 
{ 
maxCost = cost;//
запомнить локальный 
//
максимум 
sOpt = s; // 
запомнить выборку 
} 
s &= ~(1<удаление из выборки 
} 
int tmp = cost - a[i].cost; 
if (tmp > maxCost) // 
попытка добавить предмет i 
if (i < n - 1) 
Opt(i + 1, weight, tmp); 
else 
{ 
maxCost = tmp;
sOpt = s; // 
запомнить выборку 
} 
} 
1 / 23

---

71 
На рисунке 3.6 представлена форма проекта, реализующего алгоритм 
нахождения оптимальной выборки.
Рис. 3.6. Форма проекта «Оптимальная выборка» 
На этой форме размещены следующие элементы управления: 
− элемент управления dataGridView1, в двух верхних строках 
которого отображаются вес и цена предметов, а в нижней – пред-
меты, включенные в оптимальную выборку; 
− кнопка «Random» для заполнения случайными значениями мас-
сивов, хранящих значения весов и стоимостей предметов;
− текстовое поле для ввода предельного веса; 
− кнопка «Найти оптимум» для вызова функции Opt(), обработчик 
события клика для которой представлен в листинге 3.15. 
Листинг 3.15. Обработчик события клика для кнопки «Найти опти-
мум» 
private void buttonOptim_Click(object sender, Even-
tArgs e) 
{ 
totC = 0; 
for (int i = 0; i < n; i++) 
{
//
обновление массива и вычисление полной 
стоимости 
a[i].weight = (int)dataGridView1[i,0].Value; 
a[i].cost = (int)dataGridView1[i,1].Value;
totC = totC+a[i].cost;
2 / 23

---

72 
dataGridView1[i,2].Value = ""; 
} 
maxWeight=Convert.ToInt32(textBox1.Text); 
//
предельный вес 
maxCost=0; 
s = 0; sOpt = 0; // 
инициализация 
Opt(0,0,TotC);
for (int i=0; i<=n-1; i++) 
if ((sOpt & (1<dataGridView1[i, 2].Value = "V"; ; 
} 
Здесь предусмотрена возможность задавать значения цены и веса 
предметов любым из трех способов: 
− ручным вводом; 
− случайными значениями; 
− случайным заполнением с последующим редактированием.
Использование рекурсии существенно ускоряет решение, поскольку 
прямой перебор потребовал бы вычисления веса и стоимости всех
2
n
– 1 возможных выборок из n предметов. В случае n = 15 число выборок 
оказывается равным 32767. В то же время, благодаря ограничениям, содер-
жащимся в функции Opt, число ее рекурсивных вызовов при указанном числе 
предметов не превышает 500.