给定一个数，找到和最小的子集大于或等于该数。

Question

我有一组正数，例如{71.28, 82.62, 148.77, 85.05, 50.76, 103.41}。

我想找到子集，使其总和大于或等于给定数字的最小值。

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

注意：我认为解决方案可能更类似于背包问题而不是子集求和。

- boofaz

---

集合中可以有负数吗？ - Jayson Boubin

@JaysonBoubin "一组正数" - Bernhard Barker

哦，我错过了。一定是周五晚上了。 - Jayson Boubin

对于暴力算法（构建所有组合），稍作优化的方法是将数组分成两个相等的部分，分别构建所有组合（如果总和超过阈值，则跟踪最佳组合），按总和排序每个组合，有一个指针指向一个数组的第一个元素，另一个指针指向另一个数组的最后一个元素，根据你在阈值的哪一侧，你要么增加前进的指针，要么减少后退的指针，以找到全局最佳组合。 - maraca

Answer 1

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

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

- Jayson Boubin