add fastSubsetSum

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}