부분 집합 합계의 변이

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)보다 큰 가장 작은 값인지 확인합니다. 그렇다면 함수에 대한 두 개의 인수를 업데이트합니다. 하나의 인수는 추적 된 합계와 우리가 조사하는 세트의 요소 사이의 차이입니다. 이 인수는 부가 가치를 계산하거나 원래 입력 번호를 기억할 필요없이 입력 값에 대한 하위 집합의 가산 값의 근접성을 제공합니다. 다른 인수는 가중치가 가장 비슷하지만 입력 번호보다 큰 현재 세트입니다. 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; 
}