подмножество, которое дает наименьшую сумму, большую или равную заданному числу

Задача о сумме подмножества и задача о рюкзаке очень похожи по своим решениям, и вы можете использовать любую из них для решения проблемы. Однако задача о рюкзаке имеет решение динамического программирования, которое немного больше подходит для решения этой конкретной проблемы. Взгляните на эту ссылку, чтобы увидеть мою отправную точку: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ Приведенное выше решение повторяет каждую перестановку набора рекурсивно, вычитая значение каждого элемента набора из начальная сумма до тех пор, пока вычитание не приведет к отрицательному значению суммы. Это представляет ситуацию, когда исследуемое подмножество имеет значение больше указанного входного числа, или в вашем примере ситуацию, когда подмножество имеет аддитивное значение больше 270. В решении DP-ранца мы просто пропускаем этот элемент набора и перемещаем на следующий. В своем решении я проверяю, является ли значение этого решения наименьшим из наблюдаемых до сих пор значением, которое больше входного числа (270 в вашем примере). если это так, я обновляю два аргумента функции. Одним из аргументов является разница между отслеживаемой суммой и элементом исследуемого нами набора. Этот аргумент дает нам близость аддитивного значения подмножества к входному числу без необходимости вычислять аддитивное значение или запоминать исходный входной номер. Другой аргумент - это текущий набор, аддитивное значение которого ближе всего к нашему входному числу, но превышает его. В C ++ этот набор хранится в ссылке std :: 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;
}