给出大于或等于给定数字的最小总和的子集

Question

我有一组（多个）正数，例如。 {71.28, 82.62, 148.77, 85.05, 50.76, 103.41}.

我想找到总和大于或等于给定数字的子集。

例如。如果最小值是 270，则结果将是 {148.77, 71.28, 50.76}，总和为 270.81。

注意：我假设解决方案可能更类似于背包而不是子集总和。

Answer 1

子集和问题和背包问题的解很相似，你可以用其中一个来解决问题。然而，背包问题有一个动态规划解决方案，它更有利于解决这个特定问题。看看这个 link 看看我的出发点： http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ 上述解决方案递归地迭代集合的每个排列，从起始总和中减去每个集合元素的值，直到减法导致总和值为负。这表示检查的子集的值大于指定输入数字的情况，或者在您的示例中，子集的附加值大于 270 的情况。在 DP 背包解决方案中，我们只是跳过该集合元素并移动到下一个。在我的解决方案中，我检查该解决方案的值是否是迄今为止看到的大于输入数字（在您的示例中为 270）的最小值。如果是，我更新函数的两个参数。一个论点是跟踪总和与我们正在检查的集合中的元素之间的差异。这个论点给了我们子集的附加值与输入数字的接近度，而无需计算附加值或记住原始输入数字。另一个参数是当前集合，其相加值最接近但大于我们的输入数字。在 C++ 中，该集合保存在 std::vector 引用中（它也可以使用集合或多重集合）。如果没有添加到大于输入数字的值的集合，则此算法 returns 一个空向量。

#include<iostream>
#include<vector>
#include<climits>
template<typename T>
void print(std::vector<T> v)
{
        for(auto i : v)
                std::cout<<i<<" ";
        std::cout<<std::endl;
}
template<typename T>
T closestVal(T sum, std::vector<T>& set, size_t n, std::vector<T> curSet, int& minSum, std::vector<T>& ret)
{
        if(n == 0 || sum == 0)
                return 0;
        if(set[n-1] >= sum) {
                if(sum-set[n-1] > minSum) {
                        minSum = sum-set[n-1];
                        std::vector<T> newSet = curSet;
                        newSet.push_back(set[n-1]);
                        ret = newSet;
                }
                return closestVal(sum, set, n-1, curSet, minSum, ret);
        }
        else {
                std::vector<T> newSet = curSet;
                newSet.push_back(set[n-1]);
                return std::max(
                        set[n-1] + closestVal(sum-set[n-1],set,n-1, newSet, minSum, ret),
                        closestVal(sum, set, n-1, curSet, minSum, ret)
                        );
        }
}
int main()
{
        std::vector<double> ms{71.28, 82.62,148.77, 85.05, 50.76, 103.41};

        std::vector<double> ret; //ret is empty, will be filled with the return value
        int i = INT_MIN; //i is instantiated to the smallest possible number

        closestVal(270.81, ms, ms.size(), {}, i, ret);

        print(ret);
        return 0;
}

给出大于或等于给定数字的最小总和的子集

subset which gives the least sum greater than or equal to a given number

algorithm

knapsack-problem

combinatorics

subset-sum