具有两个极限的最大对数算法

提问者：小点点

具有两个极限的最大对数算法

我猜想，这样的算法已经存在了。

我有两个（或更多，但对于这个问题，两个就足够了）限制，例如，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}）

共2个答案

匿名用户

自下而上动态编程的朴素搜索空间似乎是O(n*limit_a*limit_b)，但这可能会得到更多的特性，这取决于输入，因此我们可能更倾向于记忆递归。

null

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

匿名用户

这是一个2D背包问题，只是利润都是1。通常的方法是生成与剪枝交错的子集，其中一个部分子解明显支配另一个。

下面的一些快速代码，为了方便起见，使用排序而不是合并。

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

在更高的维度中，剪枝变得更加复杂。维度的诅咒也起作用，因为支配关系变得稀疏。在这里，整数编程可能是一个更好的解决方案。