Toy problemsは役立たずか(Floydの問題・ネタバレ) http://blog.unfindable.net/archives/6103
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Are Toy Problems Useful? | |
//in Selected Papers on Computer Science by Knuth (p.172) | |
#include <iostream> | |
#include <sstream> | |
#include <iomanip> | |
#include <vector> | |
#include <set> | |
#include <unordered_map> // faster than map | |
#include <algorithm> | |
#include <ctime> | |
//#define SQRT sqrtl | |
//typedef long double real; | |
#define SQRT sqrt | |
typedef double real; | |
typedef unsigned int uint; | |
using namespace std; | |
const real DELTA = 1000.; | |
const uint N = 50; | |
const uint sizeA = 20; | |
int getKey(real x) | |
{ | |
return static_cast<int>((x - floor(x)) * 1e8); | |
} | |
real getSum(uint code, vector<real>* group, bool ignoreLast) | |
{ | |
real sum = 0; | |
uint size = group->size(); | |
if (ignoreLast) --size; | |
for (uint i = 0; i < size; ++i) if (code >> i & 1) sum += (*group)[i]; | |
return sum; | |
} | |
void printSolution(set<int>* solution) | |
{ | |
real sum = 0; | |
stringstream ss; | |
for (auto i : *solution) { | |
sum += SQRT(i); | |
ss << i << ","; | |
} | |
string str = ss.str(); | |
cout << setprecision(30) << sum << ": {" << str.substr(0, str.size()-1) << "}" << endl; | |
} | |
int main() | |
{ | |
auto start = clock(); | |
real dummy; | |
real goal = 0; | |
vector<int> all, a, b, c; | |
vector<real> groupA, groupB, groupC; //å¹³æ¹æ ¹ãè¨ç®ãã¦ãã | |
for (uint i = 1; i <= N; ++i) { | |
all.push_back(i); //{1, 2, ..., 50} | |
real t = SQRT(i); | |
goal += t; | |
if (t == floor(t)) { | |
c.push_back(i); //{1, 4, 9, 16, 25, 36, 49} | |
groupC.push_back(t); | |
} | |
else if (a.size() < sizeA) { | |
a.push_back(i); //{2, 3, 5, 6, 7, 8, 10, 11, 12, 13,... | |
groupA.push_back(t); | |
} | |
else { | |
b.push_back(i); | |
groupB.push_back(t); | |
} | |
} | |
goal /= 2.; | |
real fracPartOfGoal = modf(goal, &dummy); | |
//aã®subset sumãè¨ç®ããè¨æ¶ãã | |
unordered_multimap<int, pair<int, real>* > subsetSumOfA; //ãã¼ï¼æ¦æ°ãå¤ï¼codeAã¨åã®ã㢠| |
for (uint codeA = 0; codeA < (1u << groupA.size()); ++codeA) { | |
real sumA = getSum(codeA, &groupA, false); | |
int key = getKey(sumA); | |
auto p = new pair<int, real>(codeA, sumA); | |
subsetSumOfA.insert(pair<int, pair<int, real>* >(key, p)); | |
} | |
//bã®subset sumãè¨ç®ãã | |
real minDelta = DELTA; | |
int codeAforMinDelta = 0, codeBforMinDelta = 0; | |
real sumAforMinDelta = 0, sumBforMinDelta = 0; | |
//#pragma omp parallel | |
for (uint codeB = 0; codeB < (1u << (groupB.size() - 1)); ++codeB) { //bã®1ã¤ã®è¦ç´ ã¯æ±ºãã¦ããã¦ãã | |
real sumB = getSum(codeB, &groupB, true); | |
real t = fabs(fracPartOfGoal - modf(sumB, &dummy)); //èå³ãããã®ã¯é常ã«è¿ãå ´åã ãã ããããã§ãã | |
auto range = subsetSumOfA.equal_range(getKey(t)); | |
for (auto i = range.first; i != range.second; ++i) { | |
int codeA = i->second->first; | |
real sumA = i->second->second; | |
real delta = fabs(fracPartOfGoal - modf(sumA, &dummy) - modf(sumB, &dummy)); | |
if (delta < minDelta) { | |
//#pragma omp critical | |
{ | |
minDelta = delta; | |
codeAforMinDelta = codeA; | |
codeBforMinDelta = codeB; | |
sumAforMinDelta = sumA; | |
sumBforMinDelta = sumB; | |
} | |
} | |
} | |
} | |
//æ´æ°é¨åãæãã | |
real sum = sumAforMinDelta + sumBforMinDelta; | |
minDelta = DELTA; | |
int codeCforMinDelta = 0; | |
for (uint codeC = 0; codeC < (1u << groupC.size()); ++codeC) { | |
real delta = fabs(goal - sum - getSum(codeC, &groupC, false)); | |
if (delta < minDelta) { | |
minDelta = delta; | |
codeCforMinDelta = codeC; | |
} | |
} | |
std::cout << setprecision(30) << goal << ": goal" << endl; | |
auto solution1 = set<int>(); //ã½ã¼ãæ¸ã¿ã«ãªã | |
auto solution2 = set<int>(); | |
for (uint i = 0; i < groupA.size(); ++i) if (codeAforMinDelta >> i & 1) solution1.insert(a[i]); | |
for (uint i = 0; i < groupB.size() - 1; ++i) if (codeBforMinDelta >> i & 1) solution1.insert(b[i]); | |
for (uint i = 0; i < groupC.size(); ++i) if (codeCforMinDelta >> i & 1) solution1.insert(c[i]); | |
set_difference(all.begin(), all.end(), solution1.begin(), solution1.end(), inserter(solution2, solution2.end())); | |
printSolution(&solution1); | |
printSolution(&solution2); | |
clock_t finish = clock(); | |
real duration = real(finish - start) / CLOCKS_PER_SEC; | |
cout << "Elapsed time: " << setprecision(3) << duration << " sec." << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment