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

Question

I have a (multi)set of positive numbers, eg. {71.28, 82.62, 148.77, 85.05, 50.76, 103.41}.

I want to find the subset which gives the least sum greater than or equal to a given number.

Eg. if the minimum was 270, then the result would be {148.77, 71.28, 50.76}, which sums to 270.81.

Note: I assume the solution might be more similar to knapsack than subset sum.

Answer 1

The subset sum problem and the knapsack problem are pretty similar in their solutions, and you could use either to solve the problem. The knapsack problem, however, has a dynamic programming solution which is a bit more conducive to solving this particular problem. Take a look at this link to see my starting point: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ The above solution iterates over each permutation of the set recursively, subtracting each set element's value from the starting sum until the subtraction would cause the sum value to be negative. This represents a situation where the subset examined has a value greater than the specified input number, or in your example, a situation where the subset has an additive value greater than 270. In the DP knapsack solution, we simply skip that set element and move onto the next one. In my solution, I check to see if that solution's value is the smallest value seen so far that is greater than the input number (270 in your example). if it is, I update two arguments to the function. One argument is the difference between the tracked sum and the element in the set we are examining. This argument gives us the proximity of the subset's additive value to the input number without having to calculate the additive value or remember the original input number. The other argument is the current set whose additive value is closest to but greater than our input number. In C++ that set is held in a std::vector reference (it could also use a set or multiset). If there is no set which adds to a value greater than the input number, this algorithm returns an empty vector.

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