Алгоритм максимального количества пар с двумя ограничениями

Question

Я предполагаю, что такой алгоритм уже существует.

У меня есть два (или больше, но для этой проблемы достаточно двух) ограничений, например limit_a = 20 limit_b = 18. Затем у меня есть несколько пар (a, b), например

(5, 5), (3, 3), (4, 2), (1, 7), (3, 2), (5 , 9), (7, 4)

Ответ должен быть 5. Пример решения: (7, 4), (3, 2), (1, 7), (4, 2) , (3, 3)

Мне нужно выбрать как можно больше пар, чтобы сумма всех элементов «a» была меньше или равна limit_a и аналогично «b». Я думал, что это проблема 2D-рюкзака, но это не так. Мое лучшее «решение» - проверить все перестановки в списке этих пар и проверить суммы. Это нормально, например, как выше, но, конечно, не с большим. Мой код C ++:

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    int limit_a = 20;
    int limit_b = 18;
    vector<pair<int, int>> vect;
    vect.push_back(make_pair(5, 5));
    vect.push_back(make_pair(3, 3));
    vect.push_back(make_pair(4, 2));
    vect.push_back(make_pair(1, 7));
    vect.push_back(make_pair(3, 2));
    vect.push_back(make_pair(5, 9));
    vect.push_back(make_pair(7, 4));
    int how_many_max = 0;
    do {
        int copy_a = limit_a;
        int copy_b = limit_b;
        int how_many = 0;
        for ( vector<pair<int,int>>::const_iterator it = vect.begin(); it != vect.end(); it++){
                copy_a -= it->first;
                copy_b -= it->second;
                if((copy_a < 0) || (copy_b < 0)) {
                    break;
                }
                how_many++;
            }
        if (how_many > how_many_max) how_many_max = how_many;
    } while(next_permutation(vect.begin(), vect.end() ));
    cout << how_many_max;
    return 0;
}

Пример:

int limit_a = 30;
int limit_b = 80;
std::vector<std::pair<int, int>> vect = {{37, 20}, {90, 45}, {76, 33}, {3, 93}, {66, 71}, {48, 21}, {8, 28}, {24, 83}, {99, 13}, {42, 52}, {81, 15}, {2, 38}, {7, 19}, {32, 65}, {70, 85}, {12, 82}, {61, 6}, {60, 31}, {46, 34}, {43, 62}, {41, 78}, {64, 80}, {88, 86}, {77, 16}, {44, 100}, {92, 57}, {40, 53}, {9, 56}, {68, 67}, {23, 11}, {35, 30}, {69, 84}, {75, 27}, {87, 26}, {50, 36}, {79, 73}, {4, 91}, {17, 98}, {51, 29}, {25, 95}, {14, 55}, {10, 58}, {54, 49}, {97, 63}, {59, 72}, {1, 39}, {18, 22}, {94, 74}, {96, 5}, {47, 89}

Должен дать 3: ({2, 38}, {7, 19}, {18, 22})

Answer 1

Это двухмерная задача о рюкзаке, только прибыль равна 1. Применяется обычный подход к генерации подмножеств, чередующихся с отсечкой, где одно частичное подрешение явно преобладает над другим. * 1001 слияние для удобства.

#include <algorithm>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

int main() {
  int limit_a = 20;
  int limit_b = 18;
  std::vector<std::pair<int, int>> vect = {{5, 5}, {3, 3}, {4, 2}, {1, 7},
                                           {3, 2}, {5, 9}, {7, 4}};
  limit_a = 30;
  limit_b = 80;
  vect = {{37, 20}, {90, 45}, {76, 33}, {3, 93},   {66, 71}, {48, 21}, {8, 28},
          {24, 83}, {99, 13}, {42, 52}, {81, 15},  {2, 38},  {7, 19},  {32, 65},
          {70, 85}, {12, 82}, {61, 6},  {60, 31},  {46, 34}, {43, 62}, {41, 78},
          {64, 80}, {88, 86}, {77, 16}, {44, 100}, {92, 57}, {40, 53}, {9, 56},
          {68, 67}, {23, 11}, {35, 30}, {69, 84},  {75, 27}, {87, 26}, {50, 36},
          {79, 73}, {4, 91},  {17, 98}, {51, 29},  {25, 95}, {14, 55}, {10, 58},
          {54, 49}, {97, 63}, {59, 72}, {1, 39},   {18, 22}, {94, 74}, {96, 5},
          {47, 89}};
  std::vector<std::vector<std::pair<int, int>>> frontier = {
      {{limit_a, limit_b}}};
  for (auto [a, b] : vect) {
    frontier.push_back({});
    for (std::size_t how_many = frontier.size() - 1; how_many > 0; how_many--) {
      std::vector<std::pair<int, int>> &level = frontier[how_many];
      for (auto [residual_a, residual_b] : frontier[how_many - 1]) {
        if (residual_a >= a && residual_b >= b)
          level.push_back({residual_a - a, residual_b - b});
      }
      if (level.empty())
        continue;
      std::sort(level.begin(), level.end(),
                std::greater<std::pair<int, int>>());
      auto output = level.begin();
      auto input = output;
      for (++input; input != level.end(); ++input) {
        if (std::tie(input->second, input->first) >
            std::tie(output->second, output->first))
          *++output = *input;
      }
      level.erase(++output, level.end());
      if ((false)) {
        for (auto [residual_a, residual_b] : level) {
          std::cout << residual_a << ',' << residual_b << ' ';
        }
        std::cout << '\n';
      }
    }
  }
  std::size_t how_many_max = frontier.size() - 1;
  while (frontier[how_many_max].empty())
    how_many_max--;
  std::cout << how_many_max << '\n';
}

В более высоких измерениях обрезка усложняется. Проклятие размерности проявляется еще и потому, что отношения доминирования становятся более разреженными. Целочисленное программирование может быть здесь лучшим решением.

Answer 2

Наивное пространство поиска для восходящего динамического программирования c кажется O(n * limit_a * limit_b), но оно может получить намного больше идиосинкразии c, в зависимости от ввода, поэтому мы могли бы, возможно, предпочесть мемоизированную рекурсию.

function f(pairs, a, b, i=0, memo={}){
  if (i == pairs.length)
    return 0;
  
  const key = String([i, a, b]);
  if (memo.hasOwnProperty(key))
    return memo[key];
    
  // Skip this pair
  let best = f(pairs, a, b, i+1, memo);
  
  const [l, r] = pairs[i];
  
  // Maybe include this pair
  if (l <= a && r <= b)
    best = Math.max(best, 1 + f(pairs, a-l, b-r, i+1, memo));
    
  return memo[key] = best;
}

var pairs = [
 [5, 5], [3, 3], [4, 2],
 [1, 7], [3, 2], [5, 9], [7, 4]
];

console.log(f(pairs, 20, 18));