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 ++++
 tcr.pdf                         | Bin 696332 -> 698834 bytes
 test/other/fastSubsetSum.cpp    |  49 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 74 insertions(+)
 create mode 100644 content/other/fastSubsetSum.cpp
 create mode 100644 test/other/fastSubsetSum.cpp

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}
diff --git a/tcr.pdf b/tcr.pdf
index 1bf4c26..d383dd9 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --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();
+}
+
-- 
cgit v1.2.3