Algorithm for max number of pairs with two limits

user_6241554 0
Viewed 154

I guess that such an algorithm already exists.

I have two (or more, but two is sufficient for this problem) limits, e.g. limit_a=20 limit_b=18. Then I have some (a, b) pairs, e.g.

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

The answer should be 5. An example of a solution: (7, 4), (3, 2), (1, 7), (4, 2), (3, 3)

I need to choose as many pairs as possible such that the sum of all "a" elements is less or equal to limit_a and analogously with "b". I thought that it is 2D Knapsack problem, but it isn't. My best "solution" is to check all permutations of the list of these pairs and check the sums. It's fine for example, like above one, but of course not with bigger one's. My C++ code:

#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;
}

Example:

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}

Should give 3: ({2, 38}, {7, 19}, {18, 22})

algorithm c++
2 Answers

It is a 2D knapsack problem, just the profits are all 1. The usual approach of generating subsets interleaved with pruning where a partial subsolution obviously dominates another applies.

Some quick code below, using sorting instead of a merge for convenience.

#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';
}

In higher dimensions, the pruning gets more complicated. The curse of dimensionality also kicks in because domination relation gets sparser. Integer programming might be a better solution here.

user_21446690

A naive search space for bottom-up dynamic programming seems to be O(n * limit_a * limit_b) but this can get a lot more idiosyncratic, depending on the input, so we could possibly favour a memoised recursion.

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));

user_20347870
Related