Определение

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

Примеры задач

Задача №1

Найдите максимальное значение набора предметов, которые можно поместить в рюкзак, не превышая его грузоподъемность. Даны $N$ предметов, каждый с весом $w_i$ и стоимостью $v_i​$. Грузоподъемность рюкзака $W$.

Решение

1. Отсортировать предметы по убыванию $v_i / w_i​$ (стоимость на единицу веса).

2. Инициализировать максимальную стоимость и текущую стоимость в ноль.

3. Использовать метод ветвей и границ для перебора предметов, отслеживая текущий вес и стоимость.

4. Для каждой ветви проверять, если текущий вес превышает грузоподъемность, то не продолжать эту ветвь.

5. Обновлять максимальную стоимость, если текущая стоимость больше.

Псевдокод

Функция ветвь_и_граница(индекс, текущий_вес, текущая_стоимость, грузоподъемность, предметы, максимальная_стоимость):    
    если индекс == количество_предметов:    
        если текущая_стоимость > максимальная_стоимость:    
            максимальная_стоимость = текущая_стоимость    
        вернуть    
    
    предмет = предметы[индекс]    
    
    если текущий_вес + предмет.вес <= грузоподъемность:    
        ветвь_и_граница(индекс + 1, текущий_вес + предмет.вес, текущая_стоимость + предмет.стоимость, грузоподъемность, предметы, максимальная_стоимость)    
    
    ветвь_и_граница(индекс + 1, текущий_вес, текущая_стоимость, грузоподъемность, предметы, максимальная_стоимость)    
    
Функция решить(грузоподъемность, предметы):    
    Отсортировать предметы по убыванию стоимости на единицу веса    
    максимальная_стоимость = 0    
    ветвь_и_граница(0, 0, 0, грузоподъемность, предметы, максимальная_стоимость)    
    вернуть максимальная_стоимость

Реализация на Python

Аннотация:    
cmp - компаратор для сортировки предметов по убыванию отношения стоимости к весу    
item - кортеж, содержащий вес и стоимость предмета    
weight - вес текущего предмета    
value - стоимость текущего предмета    
branch_and_bound - рекурсивная функция, реализующая метод ветвей и границ для поиска максимальной стоимости набора предметов    
items - список предметов, где каждый предмет представлен кортежем (вес, стоимость)    
capacity - максимальная грузоподъемность рюкзака    
current_weight - текущий вес предметов в рюкзаке    
current_value - текущая стоимость предметов в рюкзаке    
max_value - текущая максимальная стоимость, которую можно получить    
solve - Функция для нахождения максимальной стоимости набора предметов, которые можно поместить в рюкзак, не превышая заданную грузоподъемность  
  
def cmp(item):    
    weight, value = item    
    return value / weight    
    
def branch_and_bound(items, capacity, index, current_weight, current_value, max_value):    
    if index == len(items):    
        if current_value > max_value[0]:    
            max_value[0] = current_value    
        return    
    
    weight, value = items[index]    
    if current_weight + weight <= capacity:    
        branch_and_bound(items, capacity, index + 1, current_weight + weight, current_value + value, max_value)    
    
    branch_and_bound(items, capacity, index + 1, current_weight, current_value, max_value)    
    
def solve(capacity, items):    
    items.sort(key=cmp, reverse=True)    
    max_value = [0]    
    branch_and_bound(items, capacity, 0, 0, 0, max_value)    
    return max_value[0]

Олимпиадная реализация на C++

Аннотация:    
Item - cтруктура для хранения информации о предмете, включая его вес и стоимость    
w - вес предмета    
v - стоимость предмета    
dfs - рекурсивная функция, реализующая метод ветвей и границ для поиска максимальной стоимости набора предметов    
items - список предметов, где каждый предмет представлен кортежем (вес, стоимость)    
cap - максимальная грузоподъемность рюкзака    
currW - текущий вес предметов в рюкзаке    
currV - текущая стоимость предметов в рюкзаке    
maxV - текущая максимальная стоимость, которую можно получить    
solve - функция для нахождения максимальной стоимости набора предметов, которые можно поместить в рюкзак, не превышая заданную грузоподъемность    
a - первый предмет для сравнения    
b - второй предмет для сравнения  
  
using namespace std;    
    
struct Item {    
    int w;    
    int v;    
};    
    
void dfs(const vector <Item> &items, int cap, int idx, int currW, int currV, int &maxV) {    
    if (idx == items.size()) {    
        if (currV > maxV)    
            maxV = currV;    
        return;    
    }    
    
    const Item &item = items[idx];    
    if (currW + item.w <= cap)    
        dfs(items, cap, idx + 1, currW + item.w, currV + item.v, maxV);    
    
    dfs(items, cap, idx + 1, currW, currV, maxV);    
}    
    
int solve(int cap, vector <Item> &items) {    
    sort(items.begin(), items.end(), [](const Item &a, const Item &b) {    
        return static_cast <double>(a.v) / a.w > static_cast <double>(b.v) / b.w;    
    });    
    int maxV = 0;    
    dfs(items, cap, 0, 0, 0, maxV);    
    return maxV;    
}

Продуктовая реализация на C++

Item - cтруктура для хранения информации о предмете, включая его вес и стоимость    
weight - вес предмета    
value - стоимость предмета    
cmp - компаратор для сортировки предметов по убыванию отношения стоимости к весу    
a - первый предмет для сравнения    
b - второй предмет для сравнения    
r1 - отношение стоимости к весу для первого предмета    
r2 - отношение стоимости к весу для второго предмета    
branch_and_bound - рекурсивная функция, реализующая метод ветвей и границ для поиска максимальной стоимости набора предметов    
items - список предметов, где каждый предмет представлен кортежем (вес, стоимость)    
capacity - максимальная грузоподъемность рюкзака    
current_weight - текущий вес предметов в рюкзаке    
current_value - текущая стоимость предметов в рюкзаке    
max_value - текущая максимальная стоимость, которую можно получить    
solve - функция для нахождения максимальной стоимости набора предметов, которые можно поместить в рюкзак, не превышая заданную грузоподъемность  
  
using namespace std;    
    
struct Item {    
  int weight;    
  int value;    
};    
    
bool cmp(const Item &a, const Item &b) {    
  double r1 = (double)a.value / a.weight;    
  double r2 = (double)b.value / b.weight;    
  return r1 > r2;    
}    
    
void branch_and_bound(const vector <Item> &items, int capacity, int index,    
                      int current_weight, int current_value, int &max_value) {    
  if (index == items.size()) {    
    if (current_value > max_value)     
      max_value = current_value;    
       
    return;    
  }    
    
  Item item = items [index];    
  if (current_weight + item.weight <= capacity) {    
    branch_and_bound(items, capacity, index + 1, current_weight + item.weight,    
                     current_value + item.value, max_value);    
  }    
    
  branch_and_bound(items, capacity, index + 1, current_weight, current_value,    
                   max_value);    
}    
    
int solve(int capacity, vector <Item> &items) {    
  sort(items.begin(), items.end(), cmp);    
  int max_value = 0;    
  branch_and_bound(items, capacity, 0, 0, 0, max_value);    
  return max_value;    
}

Задача №2

Задача: Найдите минимальное количество монет, которые необходимо использовать, чтобы набрать сумму $S$ из набора монет с номиналами $c_1, c_2,... c_n$​.

Решение

1. Отсортировать монеты по убыванию номинала.

2. Инициализировать минимальное количество монет как бесконечность.

3. Использовать метод ветвей и границ для перебора количества монет, отслеживая текущую сумму и количество монет.

4. Для каждой ветви проверять, если текущая сумма превышает $S$, то не продолжать эту ветвь.

5. Обновлять минимальное количество монет, если текущая сумма равна $S$.

Псевдокод

Функция ветвь_и_граница(индекс, текущая_сумма, количество_монет, монеты, целевая_сумма, минимальное_количество):    
    если текущая_сумма == целевая_сумма:    
        если количество_монет < минимальное_количество:    
            минимальное_количество = количество_монет    
        вернуть    
        
    если индекс == длина(монеты) или текущая_сумма > целевая_сумма:    
        вернуть    
    
    монета = монеты [индекс]    
    максимальное_использование = (целевая_сумма - текущая_сумма) // монета    
    
    для i от 0 до максимальное_использование:    
        ветвь_и_граница(индекс + 1, текущая_сумма + i * монета, количество_монет + i, монеты, целевая_сумма, минимальное_количество)    
    
Функция решить(целевая_сумма, монеты):    
    Отсортировать монеты по убыванию номинала    
    минимальное_количество = бесконечность    
    ветвь_и_граница(0, 0, 0, монеты, целевая_сумма, минимальное_количество)    
    вернуть минимальное_количество

Реализация на Python

Аннотация:    
branch_and_bound - рекурсивная функция, реализующая метод ветвей и границ для поиска минимального количества монет    
coins - список номиналов доступных монет    
target_sum - целевая сумма, которую необходимо набрать    
current_sum - текущая сумма набранных монет    
num_coins - текущее количество использованных монет    
min_coins - минимальное количество монет, необходимое для набора целевой суммы    
coin - номинал текущей монеты    
max_use - максимальное количество раз, которое можно использовать текущую монету    
solve - функция для нахождения минимального количества монет, необходимых для набора заданной суммы  
  
def branch_and_bound(coins, target_sum, index, current_sum, num_coins, min_coins):    
    if current_sum == target_sum:    
        min_coins[0] = min(min_coins[0], num_coins)    
        return    
    
    if index == len(coins) or current_sum > target_sum:    
        return    
    
    coin = coins[index]    
    max_use = (target_sum - current_sum) // coin    
    
    for i in range(max_use + 1):    
        branch_and_bound(coins, target_sum, index + 1, current_sum + i * coin, num_coins + i, min_coins)    
    
def solve(target_sum, coins):    
    coins.sort(reverse=True)    
    min_coins = [float('inf')]    
    branch_and_bound(coins, target_sum, 0, 0, 0, min_coins)    
    return min_coins[0]

Олимпиадная реализация на C++

Аннотация:    
typedef - переопределение имени типа данных    
dfs - рекурсивная функция, реализующая метод ветвей и границ для поиска минимального количества монет    
cs - список номиналов доступных монет    
target - целевая сумма, которую необходимо набрать    
currSum - текущая сумма набранных монет    
numCs - текущее количество использованных монет    
minCs - минимальное количество монет, необходимое для набора целевой суммы    
c - номинал текущей монеты    
maxUse - максимальное количество раз, которое можно использовать текущую монету    
solve - функция для нахождения минимального количества монет, необходимых для набора заданной суммы  
  
typedef vector <int> vi;    
    
void dfs(const vi &cs, int target, int idx, int currSum, int numCs,    
         int &minCs) {    
  if (currSum == target) {    
    minCs = min(minCs, numCs);    
    return;    
  }    
    
  if (idx == cs.size() || currSum > target) return;    
    
  int c = cs [idx];    
  int maxUse = (target - currSum) / c;    
    
  for (int i = 0; i <= maxUse; ++i) {    
    dfs(cs, target, idx + 1, currSum + i * c, numCs + i, minCs);    
  }    
}    
    
int solve(int target, vi &cs) {    
  sort(cs.rbegin(), cs.rend());    
  int minCs = INT_MAX;    
  dfs(cs, target, 0, 0, 0, minCs);    
  return minCs;    
}

Продуктовая реализация на C++

Аннотация:    
branch_and_bound - рекурсивная функция, реализующая метод ветвей и границ для поиска минимального количества монет    
coins - список номиналов доступных монет    
target_sum - целевая сумма, которую необходимо набрать    
current_sum - текущая сумма набранных монет    
num_coins - текущее количество использованных монет    
min_coins - минимальное количество монет, необходимое для набора целевой суммы    
coin - номинал текущей монеты    
max_use - максимальное количество раз, которое можно использовать текущую монету    
solve - функция для нахождения минимального количества монет, необходимых для набора заданной суммы  
  
using namespace std;    
    
void branch_and_bound(const vector <int> &coins, int target_sum, int index,    
                      int current_sum, int num_coins, int &min_coins) {    
  if (current_sum == target_sum) {    
    if (num_coins < min_coins)     
      min_coins = num_coins;    
    
    return;    
  }    
    
  if (index == coins.size() || current_sum > target_sum)    
    return;    
    
  int coin = coins [index];    
  int max_use = (target_sum - current_sum) / coin;    
    
  for (int i = 0; i <= max_use; ++i) {    
    branch_and_bound(coins, target_sum, index + 1, current_sum + i * coin,    
                     num_coins + i, min_coins);    
  }    
}    
    
int solve(int target_sum, vector <int> &coins) {    
  sort(coins.rbegin(), coins.rend());    
  int min_coins = INT_MAX;    
  branch_and_bound(coins, target_sum, 0, 0, 0, min_coins);    
  return min_coins;    
}