Определение

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

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

Задача №1

Грузоподъемность машины $M$ килограмм. Есть $N$ ящиков с грузами, масса $i$-го ящика равна целому положительному числу $mi$. Определите, какую наибольшую массу грузов можно увезти на автомобиле.

Решение

Первое действие - это сортировка масс грузов в порядке невозрастания.

Заведём переменную $weight$, в которую будем хранить текущую массу грузов в машине.

Далее перебираем массы грузов и добавляем их в $weight$. Если при добавлении груза $weight$ станет больше чем $M$, выходим из цикла. Текущее значение $weight$ наш ответ.

Псевдокод

Функция решить(грузоподъемность, массы\_ящиков):    
    Отсортировать массы\_ящиков в порядке невозрастания    
    текущая\_масса = 0    
    
    Для каждого масса в массы\_ящиков:    
        Если текущая\_масса + масса \<= грузоподъемность:    
            текущая\_масса = текущая\_масса + масса    
        Иначе:    
            Выйти из цикла    
    
    Вернуть текущая\_масса

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

Аннотация:    
solve - функция, которая реализует алгоритм перебора порядка    
M - максимальная грузоподъемность машины в килограммах    
box\_weights - список весов ящиков, доступных для погрузки    
weight - текущая масса грузов, погруженных в машину    
w - текущий вес ящика   
  
def solve(M, box\_weights):      
    box\_weights.sort(reverse=True)      
        
    weight = 0      
    for w in box\_weights:      
        if weight + w \< M:      
            weight += w      
                  
        else:      
            break      
      
    return weight   

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

typedef - переопределение имени типа данных    
solve - функция, которая реализует алгоритм перебора порядка    
M - максимальная грузоподъемность машины в килограммах    
arr - список весов ящиков, доступных для погрузки    
weight - текущая масса грузов, погруженных в машину    
w - текущий вес ящика   
  
typedef vector\<int\> vi;    
    
int solve(int M, vi arr) \{    
  sort(arr.rbegin(), arr.rend());    
    
  int weight = 0;    
  for (int w : arr) \{    
    if (weight + w \< M) \{    
      weight += w;    
    \} else \{    
      break;    
    \}    
  \}    
  return weight;    
\}

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

Аннотация:    
solve - функция, которая реализует алгоритм перебора порядка    
M - максимальная грузоподъемность машины в килограммах    
box\_weights - список весов ящиков, доступных для погрузки    
weight - текущая масса грузов, погруженных в машину    
w - текущий вес ящика   
  
int solve(int M, std::vector\<int\> box\_weights) \{    
  std::sort(box\_weights.rbegin(), box\_weights.rend());    
    
  int weight = 0;    
  for (int w : box\_weights) \{    
    if (weight + w \< M) \{    
      weight += w;    
    \} else \{    
      break;    
    \}    
  \}    
  return weight;    
\}

Задача №2

Дана емкость рюкзака $C$ литров. Есть $N$ контейнеров с жидкостями, объем $i$-го контейнера равен целому положительному числу $vi$. Определите, какой наибольший объем жидкости можно поместить в рюкзак.

Решение

Первое действие - это сортировка объемов жидкостей в порядке невозрастания.

Заведём переменную $volume$, в которую будем хранить текущий объем жидкости в рюкзаке.

Далее перебираем объемы жидкостей и добавляем их в $volume$,. Если при добавлении объема $volume$ станет больше чем $C$, выходим из цикла. Текущее значение $volume$ наш ответ.

Псевдокод

Функция решить(емкость, объемы\_контейнеров):    
    Отсортировать объемы\_контейнеров в порядке невозрастания    
    текущий\_объем = 0    
    
    Для каждого объем в объемы\_контейнеров:    
        Если текущий\_объем + объем \<= емкость:    
            текущий\_объем = текущий\_объем + объем    
        Иначе:    
            Выйти из цикла    
    
    Вернуть текущий\_объем

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

Аннотация:    
solve - функция, которая реализует алгоритм перебора порядка    
C - максимальная емкость рюкзака в литрах    
container\_volumes - список объемов контейнеров с жидкостью, доступных для погрузки    
volume - текущий объем жидкости в рюкзаке    
V - текущий объем контейнера  
  
def solve(C, container\_volumes):    
    container\_volumes.sort(reverse=True)    
        
    volume = 0    
    for v in container\_volumes:    
        if volume + v \<= C:    
            volume += v    
                
        else:    
            break    
        
    return volume

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

Аннотация:    
typedef - переопределение имени типа данных    
solve - функция, которая реализует алгоритм перебора порядка    
c - максимальная емкость рюкзака в литрах    
volumes - список объемов контейнеров с жидкостью, доступных для погрузки    
vol - текущий объем жидкости в рюкзаке    
V - текущий объем контейнера  
  
typedef vector\<int\> vi;    
    
int solve(int c, vi volumes) \{    
    sort(volumes.rbegin(), volumes.rend());    
    
    int vol = 0;    
    for (int v : volumes) \{    
        if (vol + v \<= c) \{    
            vol += v;    
        \} else \{    
            break;    
        \}    
    \}    
    return vol;    
\}

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

Аннотация:    
solve - функция, которая реализует алгоритм перебора порядка    
capacity - максимальная емкость рюкзака в литрах    
container\_volumes - список объемов контейнеров с жидкостью, доступных для погрузки    
volume - текущий объем жидкости в рюкзаке    
V - текущий объем контейнера  
  
int solve(int capacity, std::vector\<int\> container\_volumes) \{    
  std::sort(container\_volumes.rbegin(), container\_volumes.rend());    
    
  int volume = 0;    
  for (int v : container\_volumes) \{    
    if (volume + v \<= capacity) \{    
      volume += v;    
    \} else \{    
      break;    
    \}    
  \}    
  return volume;    
\}