1. General topic
We have N (N<=35) elements, select a subset from them so that the absolute value of the sum of its elements is the smallest. If there are multiple feasible solutions, select the one with the smallest elements.
Output the absolute value of the sum of elements in the optimal subset, and the number of elements in the optimal subset.
2. Problem-solving ideas
We consider the first half and the second half of the array separately.
We use the binary increment idea (0001,0010,0011…1111) to calculate the sum of all subsets of the second half of the array (removing the empty set), and record the number of elements in each subset.
Then sort according to the sum of the subsets, and then use double pointers to update the number of elements of all subsets with equal sums to the smallest number of elements with the same sum.
Then use binary enumeration of the first half of the array (including the empty set). For each element of the left half and leftSum, go to the second half of the array to find -leftSum. (The idea of this dichotomy is to find the smallest subset element of the second half. The sum is not less than the first subscript of -leftSum), and then judge the bisection results idx and idx-1, and calculate the absolute value of the sum of the left and right subsets and the number of elements. Update ans.
It should be noted that we have removed the case where the right side is the empty set, so we need to make an additional judgment on the case where only the elements on the left are used.
I am also very good at this question. I have answered this question more than 60 times and spent 6 days writing it. In the end, I definitely no longer need pairs. I write the structure myself and no longer use lower_bound. I write the two points myself, and then combine it with the ruler calculation method I came up with. Got this question.
During the process, I did not check the solution or search for the answer, but I did look at the source code of pair and Comparator in STL, and also looked at the source code of the “Oversized Knapsack Problem” in “Challenge Programming”. In fact, I shouldn’t look at these. It affected the progress and thinking process. After reading the STL source code and the white paper, I decided not to use pair and lower_bound. I implemented the handwritten two-part bottom layer and optimized the handwritten double pointer. After all, I passed it.
It can be said that I am very good at it. I will share a set of code that I summarized by myself below.
After passing it, I checked the solution and found that my map and their map were more complicated because they used custom structures, double pointers and handwritten bisection bottom-level implementation, but it was probably 5 times faster than it. I will share the source code with everyone.
3. Code
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Node
{
int cnt;
ll sum;
Node(ll sum = 0LL, int cnt = 0) : sum(sum), cnt(cnt) {}
};
Node rightNodes[262150];
int towPow[27], n, rightLen, leftLen, rightPow, leftPow, ansCnt;
ll num[40], ans, inf = 0x3f3f3f3f3f3f3f3fLL;
void initTwoPow()
{
towPow[0] = 1;
for (int i = 1; i <= 21; i + + )
{
towPow[i] = towPow[i - 1] * 2;
}
}
bool compareNode(const Node & amp;a, const Node & amp;b)
{
return a.sum < b.sum;
}
ll absVal(ll a)
{
if (a >= 0LL)
{
return a;
}
else
{
return a * (-1LL);
}
}
void input()
{
ans = 0LL;
for (int i = 0; i < n; i + + )
{
scanf("%lld", & amp;num[i]);
ans = ans + num[i];
}
ans = absVal(ans);
ansCnt = n;
leftLen = n / 2;
rightLen = n - leftLen;
leftPow = towPow[leftLen];
rightPow = towPow[rightLen];
}
void calcRightSubsetBesideEmptySet()
{
for (int i = 1; i < rightPow; i + + )
{
rightNodes[i - 1].sum = 0LL;
rightNodes[i - 1].cnt = 0;
for (int j = 0; j < rightLen; j + + )
{
if ((i & amp; towPow[j]) == towPow[j])
{
rightNodes[i - 1].sum = rightNodes[i - 1].sum + num[leftLen + j];
rightNodes[i - 1].cnt = rightNodes[i - 1].cnt + 1;
}
}
}
rightNodes[rightPow - 1].sum = inf;
rightNodes[rightPow - 1].cnt = n + 1;
sort(rightNodes, rightNodes + rightPow, compareNode);
}
void minimizeCntByTwoPosinter()
{
int l = 0, r = 1, optCnt = -1;
while(true)
{
while (r < rightPow & amp; & amp; rightNodes[r].sum != rightNodes[l].sum)
{
l + + ;
r + + ;
}
optCnt = rightNodes[l].cnt;
while (r < rightPow & amp; & amp; rightNodes[r].sum == rightNodes[l].sum)
{
optCnt = min(optCnt, rightNodes[r].cnt);
r + + ;
}
while ((l + 1) < r)
{
rightNodes[l + + ].cnt = optCnt;
}
if (r == rightPow)
{
break;
}
}
}
int binarySearch(ll leftSum)
{
int l = -1, r = rightPow;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (rightNodes[mid].sum < leftSum)
{
l = mid;
}
else
{
r = mid;
}
}
return (l + 1);
}
void solve()
{
ll lSum = 0LL;
int lCnt = 0;
for (int i = 0; i < leftPow; i + + )
{
lSum = 0LL;
lCnt = 0;
for (int j = 0; j < leftLen; j + + )
{
if ((i & amp; towPow[j]) == towPow[j])
{
lSum = lSum + num[j];
lCnt = lCnt + 1;
}
}
if (lCnt != 0 & amp; & amp; absVal(lSum) < ans)
{
ans = absVal(lSum);
ansCnt = lCnt;
}
else if (lCnt != 0 & amp; & amp; absVal(lSum) == ans & amp; & amp; lCnt < ansCnt)
{
ansCnt = lCnt;
}
int idx = binarySearch(lSum * (-1LL));
if ((idx + 1) < rightPow & amp; & amp; absVal(rightNodes[idx].sum + lSum) < ans)
{
ans = absVal(rightNodes[idx].sum + lSum);
ansCnt = rightNodes[idx].cnt + lCnt;
}
else if ((idx + 1) < rightPow & amp; & amp; absVal(rightNodes[idx].sum + lSum) == ans & amp; & amp; (rightNodes[idx].cnt + lCnt) < ansCnt)
{
ansCnt = rightNodes[idx].cnt + lCnt;
}
idx--;
if (idx >= 0 & amp; & amp; absVal(rightNodes[idx].sum + lSum) < ans)
{
ans = absVal(rightNodes[idx].sum + lSum);
ansCnt = rightNodes[idx].cnt + lCnt;
}
else if (idx >= 0 & amp; & amp; absVal(rightNodes[idx].sum + lSum) == ans & amp; & amp; (rightNodes[idx].cnt + lCnt) < ansCnt)
{
ansCnt = rightNodes[idx].cnt + lCnt;
}
}
}
int main()
{
initTwoPow();
while(true)
{
scanf("%d", & amp;n);
if(n==0)
{
break;
}
input();
calcRightSubsetBesideEmptySet();
minimizeCntByTwoPosinter();
solve();
printf("%lld %d\\
", ans, ansCnt);
}
return 0;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 53794 people are learning the system