variation de somme sous-ensemble problеm

Question

I ont une (multi) ensemble de nombres positifs, par exemple. {71.28, 82.62, 148.77, 85.05, 50.76, 103.41}.

Je veux trouver le sous-ensemble qui donne le moindre somme supérieure ou égale à un nombre donné.

Par exemple. si le minimum était 270, le résultat serait {148.77, 71.28, 50.76}, qui résume à 270.81.

Note: Je suppose que la solution pourrait être plus semblable à la somme que sous-ensemble SAC A DOS.

Answer 1

Le problème de la somme sous-ensemble et le problème de havresac sont assez similaires dans leurs solutions, et vous pouvez utiliser soit pour résoudre le problème. Le problème de sac à dos, cependant, a une solution de programmation dynamique qui est un peu plus propice à la résolution de ce problème particulier. Jetez un oeil à ce lien pour voir mon point de départ: http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ La solution itère ci-dessus sur chaque permutation de l'ensemble récursive, en soustrayant la valeur de chaque élément de jeu de la somme de départ jusqu'à ce que la soustraction provoquerait la valeur de somme négative. Cela représente une situation où le sous-ensemble examiné a une valeur supérieure au nombre d'entrée spécifié, ou dans votre exemple, une situation où le sous-ensemble a une valeur additive supérieure à 270. Dans la solution de sac à dos DP, nous sautons simplement cet élément sur le prochain. Dans ma solution, je vérifie pour voir si la valeur de cette solution est la plus petite valeur vue jusqu'ici qui est plus grande que le nombre d'entrée (270 dans votre exemple). si c'est le cas, je mets à jour deux arguments à la fonction. Un argument est la différence entre la somme suivie et l'élément de l'ensemble que nous examinons. Cet argument nous donne la proximité de la valeur additive du sous-ensemble au numéro d'entrée sans devoir calculer la valeur additive ou se souvenir du numéro d'entrée original. L'autre argument est l'ensemble courant dont la valeur additive est la plus proche mais plus grande que notre nombre d'entrée. En C++, cet ensemble est maintenu dans une référence std :: vector (il peut aussi utiliser un ensemble ou un multiset). S'il n'y a pas d'ensemble qui ajoute à une valeur supérieure au nombre d'entrée, cet algorithme renvoie un vecteur vide.

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