숫자 목록이 주어지면 lst = [1, 1, 2, 4, 3, 2, 1, 1, 1, 2, 1, 4, 3, 1]
4보다 작거나 같은 이상적인 목록 수를 어떻게 찾을 수 있습니까?
여기에는 많은 가능성이 있습니다. 목표는 가능한 목록의 수를 최소화하는 것입니다. 프로그램은 다음과 같은 하위 집합 목록을 만들어야 {4}, {4}, {3, 1}, ... , {1, 1}
합니다..
마지막 목록 하위 집합이 4와 같지 않지만 그보다 작은 지 확인하십시오. 이 문제는 다음과 같은 이유로 어렵습니다.
subset-sums
합계보다 작거나 같은 것을 찾을 수 있어야합니다.여기 내 시도가 있습니다. 일반적인 아이디어는 목록을 정렬하고 왼쪽과 오른쪽으로 이동하여 매 반복마다 탐욕스럽게 가장 큰 하위 집합을 선택하는 것입니다. 시간 복잡성은 O(n)
.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> lst{1, 1, 2, 4, 3, 2, 1, 1, 1, 2, 1, 4, 3, 1};
std::sort(lst.begin(),lst.end()); //sort the list
int target = 4;
int left = 0;
int right = lst.size()-1;
std::vector<std::vector<int>> solutions;
while (left<right ){
if(lst[left] > target) // break if no solutions
break;
if(lst[right] > target) // ignore larger right values
right--;
if(lst[right]<=target){ // while the total sum is less than target, keep adding the elements
std::vector<int> subset;
subset.push_back(lst[right]);
int sum = lst[right];
while(left<right && lst[left]+sum<=target){
sum+=lst[left];
subset.push_back({lst[left]});
left++;
}
solutions.push_back(subset);
right--;
}
}
for(auto& ss : solutions){
std::cout<<'{';
for(auto n:ss){
std::cout<<n<<',';
}
std::cout<<"\b}";
std::cout<<std::endl;
}
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다