diff options
| -rw-r--r-- | content/other/fastSubsetSum.cpp | 21 | ||||
| -rw-r--r-- | content/other/other.tex | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 696332 -> 698834 bytes | |||
| -rw-r--r-- | test/other/fastSubsetSum.cpp | 49 |
4 files changed, 74 insertions, 0 deletions
diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp new file mode 100644 index 0000000..84396f6 --- /dev/null +++ b/content/other/fastSubsetSum.cpp @@ -0,0 +1,21 @@ +int fastSubsetSum(vector<int> w, int t){ + int a = 0, b = 0; + while(b < sz(w) && a + w[b] <= t) a += w[b++]; + if(b == sz(w)) return a; + int m = *max_element(all(w)); + vector<int> dp(2*m, -1), old; + dp[m+a-t] = b; + for(int i = b; i < sz(w); i++){ + old = dp; + for(int j = 0; j < m; j++){ + dp[j+w[i]] = max(dp[j+w[i]], old[j]); + } + for(int j = 2*m-1; j > m; j--){ + for(int k = max(old[j], 0); k < dp[j]; k++){ + dp[j-w[k]] = max(dp[j-w[k]], k); + } + } + } + for(a = t; dp[m+a-t] < 0; a--); + return a; +}
\ No newline at end of file diff --git a/content/other/other.tex b/content/other/other.tex index e8d8041..368d0b3 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -102,6 +102,10 @@ \textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
\sourcecode{other/recover.cpp}
+\subsection{Fast Subset Sum}
+\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}
+Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+\sourcecode{other/fastSubsetSum.cpp}
\begin{algorithm}[optional]{Zeileneingabe}
\sourcecode{other/split.cpp}
Binary files differdiff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp new file mode 100644 index 0000000..c61b1ea --- /dev/null +++ b/test/other/fastSubsetSum.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +#include <other/fastSubsetSum.cpp> + +int subsetSum(vector<int> w, int t){ + vector<bool> dp(t+1); + dp[0] = true; + for(int x : w){ + for(int i = t; i >= x; i--){ + dp[i] = dp[i] || dp[i-x]; + } + } + int ma = 0; + for(int i = 0; i <= t; i++){ + if(dp[i]) ma = i; + } + return ma; +} + +void stress_test() { + int queries = 0; + for (int test = 0; test < 10'000; test++) { + int n = Random::integer<int>(1, 20); + int t = Random::integer<int>(1, 500); + vector<int> w = Random::integers<int>(n, 0, 50); + int got = fastSubsetSum(w, t); + int expected = subsetSum(w, t); + if(got != expected) cerr << "got: " << got << " expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void performance_test() { + timer t; + int n = 10'000, a = 10'000; + vector<int> w = Random::integers<int>(n, 0, a); + int target = 10'000'000; + t.start(); + hash_t hash = fastSubsetSum(w, target); + t.stop(); + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +int main() { + stress_test(); + performance_test(); +} + |