子集和问题和背包问题在解决方案上非常相似,您可以使用其中任何一种来解决问题。然而,背包问题有一个动态规划解决方案,更有助于解决这个特定的问题。请查看此链接以查看我的起点:
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;
int i = INT_MIN;
closestVal(270.81, ms, ms.size(), {}, i, ret);
print(ret);
return 0;
}