題目大意

????給定N（N<=35)個數字，每個數字都<= 2^15. 其中一個或多個數字加和可以得到s，求出s的絕對值的最小值，并給出當s取絕對值最小值時，需要加和的數字的個數。

題目分析

????需要枚舉集合的所有情況，2^35，會超時。考慮使用折半枚舉的方法，考慮前 N/2個數字構成的集合S1，在S1中進行所有情況枚舉，復雜度為 2^17，并將所有可能的和sum以及構成和sum需要的數字個數count存放在map M中；然后在S2中進行所有情況的枚舉，復雜度為2^17，對于每種情況的sum2，在M中查找 -sum2的位置，在該位置前后位置處進行查找，求和的最小值。?
????還需要考慮，當s只有S1中的數字構成或者s只有S2中的數字構成，或者s由S1和S2中的數字構成的三類情況。?
????總的時間復雜度為 O(2^17 + 2^17*log(2^17)) = O(2^22)

實現(c++)

#include<stdio.h> #include<string.h> #include<algorithm> #include<string> #include<cmath> #include<iostream> #include<map> using namespace std;long long int ll_abs(long long int n){if (n >= 0)return n;return -n; } long long int an[40];map<long long int, int> sum_map; int main2(){int n;while (scanf("%d", &n) && n){map<long long int, int>::iterator it;sum_map.clear();for (int i = 0; i < n; i++){scanf("%lld", &an[i]);}long long int min_sum = ll_abs(an[0]);int min_count = 1;int m = n / 2;for (int i = 0; m > 0 && i < (1 << m); i++){long long int sum = 0;int count = 0;int t = i;for (int k = 0; k < m; k++){if (t & 1){sum += an[k];count++;}t >>= 1;}if (count == 0)continue;if (sum_map.find(sum) != sum_map.end()){sum_map[sum] = min(sum_map[sum], count);}elsesum_map[sum] = count;if (ll_abs(sum) < min_sum){min_sum = ll_abs(sum);min_count = count;}else if (ll_abs(sum) == min_sum){min_count = min(min_count, count);}}m = n / 2 + n % 2;for (int i = 0; i < (1 << m); i++){long long int sum = 0;int count = 0;int t = i;for (int k = 0; k < m; k++){if (t & 1){sum += an[n / 2 + k];count++;}t >>= 1;}if (count == 0)continue;if (ll_abs(sum) < min_sum){min_sum = ll_abs(sum);min_count = count;}else if (ll_abs(sum) == min_sum){min_count = min(min_count, count);}it = sum_map.lower_bound(-sum);if (it != sum_map.end()){long long int s = sum + it->first;if (ll_abs(s) < min_sum){min_sum = ll_abs(s);min_count = it->second + count;}else if (ll_abs(s) == min_sum){min_count = min(min_count, it->second + count);}}if (it != sum_map.begin()){--it;long long int s = sum + it->first;if (ll_abs(s) < min_sum){min_sum = ll_abs(s);min_count = it->second + count;}else if (ll_abs(s) == min_sum){min_count = min(min_count, it->second + count);}}}printf("%lld %d\n", min_sum, min_count);}return 0; }

?

轉載于:https://www.cnblogs.com/gtarcoder/p/4909448.html

總結

以上是生活随笔為你收集整理的poj_3977 折半枚举的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。