3 ms·
I think what you're describing is called the knapsack problem, so I'd guess the answer is no. The best you could do is randomly order the files and compress the
by castratikron 11y ago
I think what you're describing is called the knapsack problem, so I'd guess the answer is no. The best you could do is randomly order the files and compress them, and do that a few times and pick the best ordering.
- js8 11y agoFirst, I am not looking for optimal solution, good approximation is perfectly valid solution. Second, what you describe is not the best you can do.
- gwern 11y agoYou can do much better than that: you can use summaries or hashes to get a short version of each file and then compare the hashes for similarity. (Much like using perceptual hashes to find similar images.) A tool that does this is 'binsort'. It's O(N^2) IIRC, because of all the pairwise comparisons, but it's usable for up to a few hundred or thousand files.