From facc5da35282ef30e5111cdc04942d118f4ae0c5 Mon Sep 17 00:00:00 2001
From: Lucas Schwebler <lucas.schwebler@gmail.com>
Date: Tue, 10 Sep 2024 23:06:28 +0200
Subject: add fastSubsetSum

---
 content/other/fastSubsetSum.cpp | 21 +++++++++++++++++++++
 content/other/other.tex         |  4 ++++
 2 files changed, 25 insertions(+)
 create mode 100644 content/other/fastSubsetSum.cpp

(limited to 'content')

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}
-- 
cgit v1.2.3