diff options
Diffstat (limited to 'content/other')
| -rw-r--r-- | content/other/fastSubsetSum.cpp | 21 | ||||
| -rw-r--r-- | content/other/other.tex | 4 |
2 files changed, 25 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}
|