サブセット合計のバリエーション

Question

私は（複数の）正の数を持っています。 {71.28, 82.62, 148.77, 85.05, 50.76, 103.41}。

より小さい合計をに与えるサブセットを見つけたいと思います。

例：最小値が270の場合、結果は{148.77, 71.28, 50.76}となり、合計は270.81になります。

注：ソリューションは、サブセット合計よりもナップザックに近いと思われます。

Answer 1

サブセットサム問題とナップザック問題は、ソリューションでは非常によく似ています。問題を解決するにはどちらかを使用できます。しかし、ナップザックの問題は、この特定の問題を解決するのに少し役立つ動的プログラミングソリューションを持っています。 http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ 上記の解法では、集合の各順列を繰り返し再帰的に反復し、減算によって合計値が負になるまで、開始集合から各集合要素の値を減算します。これは、検査されたサブセットが指定された入力番号より大きい値を持つ状況、または例ではサブセットの値が270より大きい状況を表します。DPナップザックソリューションでは、単にその要素をスキップし、次のものへ。私のソリューションでは、そのソリューションの値が入力番号（例では270）より大きい、これまでに見た最小の値であるかどうかを確認します。そうであれば、私は関数に2つの引数を更新します。 1つの議論は、トラッキングされた合計と、調査中の集合内の要素との間の差である。この引数は、加算値を計算したり元の入力番号を覚えたりせずに、サブセットの加算値と入力数の近さを示します。もう1つの引数は、加算値が入力番号に最も近いが入力番号よりも大きい現在の集合です。 C++では、setは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; 
}