找到多个值最接近某一极限的组合的算法是什么？

Question

请告诉我，解决此类问题的有效算法是什么：

1)有一个限号(例如100)

2)有多名候选人(例如10、15、90、70、55)

( a)我们需要选择1对i，j，以便ith和jth的求和最接近于<=number。

b)我们需要选择i，j，k，.和最近但<=number的烛光

只是给我提示，读些什么，但如果你是好心的，我很感激你的解释，谢谢你

Answer 1

用于一对的情况：

• 您可以在O(NlogN)时间复杂度中找到该解决方案；其中N是元素列表的大小。
• 简单地对列表排序
• 然后从左侧选取元素，并尝试使用二进制搜索找到剩余的值(键选中)。尝试找到最接近剩余值的值，但不超过它。
• 对所有N个元素执行此操作，您将找到与求和<=键的和最近的对。

下面我将在C++中提供一个示例实现

#include <bits/stdc++.h>
using namespace std;
#define NEG_INFINITY -999999

//In order to find a pair from item[] where the sumOfPair() <= key
pair<int,int> findPair(int* item, int len, int key)
{
    int* startAddr = item;
    int* endAddr = item + len;
    int firstElement, remaining;

    //Sort the given list
    sort(startAddr, endAddr);

    int closestFoundSum = NEG_INFINITY;
    int temporarySum;
    pair<int,int> pairForClosestSum = make_pair(NEG_INFINITY, NEG_INFINITY);
    pair<int,int> temporaryPair;

    /**
     * As the list is now sorted
        * for each element in the list starting from the left
        *   binary search for the remaining number in the remaining right partition of the list
        *   if any valid element is found
        *       check the sum, and always keep the largest sum that is <= key
    **/
    for(int i=0; i < len-1; i++)
    {
        firstElement = item[i];
        remaining = key - firstElement;
        startAddr = &(item[i]) + 1;

        int* foundAddr = lower_bound(startAddr, endAddr, remaining);

        if(foundAddr >= endAddr) foundAddr--;

        if(*foundAddr > remaining && foundAddr - 1 >= startAddr){
            temporarySum = firstElement + *(foundAddr-1);
            temporaryPair = make_pair(firstElement, *(foundAddr-1));
        }
        else if(*foundAddr == remaining && foundAddr >= startAddr){
            temporarySum = firstElement + *foundAddr;
            temporaryPair = make_pair(firstElement, *foundAddr);
        }

        if(temporarySum > closestFoundSum){
            closestFoundSum = temporarySum;
            pairForClosestSum = temporaryPair;
        }
    }

    //return the pair with the greatest Sum <= key
    return pairForClosestSum;
}


int main() {
    int item[] = {15,10,79,89,110};
    int len = 5;
    int key = 100;

    //For problem (a): Find a pair in the list with the closest sum to key; where sum <= key
    pair<int,int> resultPair = findPair(item, len, key);
    cout<<"Closest Sum of a Pair: " << resultPair.first<<" + "<<resultPair.second<<" = "<< resultPair.first + resultPair.second<<endl;

}   

对于第二种情况，找到最接近的和，从列表中提取任意数量的元素:这是一个经典的0/1背包问题。这是一个动态规划问题，在这里有很好的解释。0/1背包

下面我将给出一个包含注释代码的示例实现：

#include <bits/stdc++.h>
using namespace std;
#define ResetArr(arr) memset(arr, -1, sizeof(arr))

#define MAX_SIZE 10
#define MAX_SUM 1000

//memoization table
int memo[MAX_SIZE][MAX_SUM];

//list of elements
int arr[MAX_SIZE];

int findClosestSum(int index, int sumUptoIndex, int endIndex, int key){
    if(index >= endIndex){
        return sumUptoIndex;
    }

    //check memo table
    if(memo[index][sumUptoIndex] != -1){
        return memo[index][sumUptoIndex];
    }

    int sumConsideringIndex = 0;
    int sumAvoidingIndex = 0;

    //Check with taking element at 'index' into solution tuple
    if(sumUptoIndex + arr[index] <= key){
        sumConsideringIndex = findClosestSum(index+1, sumUptoIndex + arr[index], endIndex, key);
    }

    //Check without taking element at 'index' into solution tuple
    sumAvoidingIndex = findClosestSum(index+1, sumUptoIndex, endIndex, key);

    //take the sum that is closest and strictly less than key
    return memo[index][sumUptoIndex] = max(sumConsideringIndex, sumAvoidingIndex);
}


int main(){
    int size = 8;
    int key = 29;

    int arr2[size] = {5, 10, 17, 11, 12, 25, 4, 2};

    //fillup the list with given elements in arr2
    memcpy(arr, arr2, size * sizeof(int));

    //Do a 0/1 Knapsack Dp
    ResetArr(memo);

    cout<< "The closest {sum | sum <= key} = " << findClosestSum(0, 0, size, key) <<endl;

}

Answer 2

提示：

对于一对，

• 对所有价值进行排序；
• 使用两个“游标”从两端进行扫描；移动左游标；如果和超出限制数，则移动右游标。

例如。

 10, 15, 55, 70, 90
  ^               ^

好了。