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

Листинг 3.13. Восемь ферзей. Поиск всех вариантов 
void Attemt(int i, ref int n) 
{ 
// 
инициализировать выбор позиции для i-ого ферзя; 
for(int j = 0; j < Size; j++) 
{ 
// 
выбор позиции i-ого ферзя 
if(NoHor[j] && NoRDiag[i+j] && NoLDiag[i-j]) 
{ 
PosQ[i] = j; / 
поставить ферзя 
21 / 23

---

68 
NoHor[j] = false; 
NoLDiag[i - j] = false; 
NoRDiag[i + j] = false; 
if(i < Size)
Attemt(i+1, ref n); 
else 
++n; 
NoHor[j] = true; // 
линии опять свободны 
NoLDiag[i - j] = true; 
NoRDiag[i + j] = true;
} 
} 
} 
Параметрами рекурсивной функции являются номер i ферзя, для кото-
рого надо найти позицию, и переменная n, используемая для подсчета общего 
числа решений. Цикл обеспечивает перебор всех возможных позиций для 
каждого из ферзей и, тем самым, нахождение всех возможных расстановок. 
3.4.2. З
АДАЧА ОПТИМАЛЬНОГО ВЫБОРА
 
Еще одним примером применения метода поиска с возвратом является 
задача оптимального выбора, т. е. поиска решения, которое может считаться 
оптимальным, удовлетворяющим некоторому, наперед заданному условию. 
Наиболее очевидной представляется стратегия, основанная на последо-
вательном переборе возможных решений с отбором на каждом этапе наи-
лучшего из уже просмотренных. Здесь очевидна аналогия с поиском мини-
мального элемента в массиве, при котором очередной элемент сравнивается с 
минимальным из ранее просмотренных и при необходимости этот «текущий» 
минимум обновляется. 
Примером задачи оптимального выбора является хорошо известная 
задача об упаковке рюкзака, формулируемая следующим образом. Имеется 
некоторое количество предметов, каждый из которых имеет определенные 
вес и стоимость. Задача состоит в том, чтобы отобрать предметы, имеющие 
наибольшую суммарную стоимость при заданном ограничении на их сум-
марный вес. Такой набор предметов будем называть оптимальной выбор-
кой. 
22 / 23

---

69 
Выборки, составляющие приемлемые решения, строятся постепенно, 
по мере рассмотрения отдельных предметов. Для каждого из предметов мож-
но принять решение о его включении либо невключении в выборку. Решение о 
включении очередного предмета принимается, если после добавления этого 
предмета суммарный вес выборки не превысит предельного веса, но ее сум-
марная стоимость станет больше ранее достигнутого максимума. Если добав-
ление любого из оставшихся предметов ведет к превышению предельного 
веса, то формирование выборки завершается. 
Данные, необходимые для решения этой задачи, описываются следую-
щим образом: 
struct TItem // 
предмет 
{ 
public int weight;
// 
вес 
public int cost;
// 
цена 
} 
static int n = 15;
// 
количество предме-
тов 
TItem[] a = new TItem[n]; 
// 
набор предметов 
int maxWeight; // 
ограничение на вес выборки 
int maxCost; // 
текущая наибольшая стоимость выборки 
int totCost; // 
текущая стоимость выборки 
int s = 0; // 
текущая выборка 
int sOpt = 0; // 
оптимальная выборка 
В переменных целого типа s и sOpt i-й бит отвечает за включение или 
не включение i-го предмета. Для хранения в памяти переменной целого типа 
требуется 4 байта или 32 бита. Предмет с номером i входит в множество, если 
i-й бит равен 1. Таким образом, целое позволяет работать с множествами до 
32 элементов. Для работы с множествами необходимо уметь выполнять три 
операции: 
− добавление i-го элемента в множество: s = s | (1 << i); 
− удаление i-го элемента из множества: s = s & ~(1< 
− проверка вхождения i-го элемента в множество: s & (1<
В листинге 3.14 представлена рекурсивная функция Opt(), выпол-
няющая поиск оптимальной выборки путем перебора различных вариантов ее 
формирования.
23 / 23

---

70