From facc5da35282ef30e5111cdc04942d118f4ae0c5 Mon Sep 17 00:00:00 2001 From: Lucas Schwebler Date: Tue, 10 Sep 2024 23:06:28 +0200 Subject: add fastSubsetSum --- content/other/fastSubsetSum.cpp | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 content/other/fastSubsetSum.cpp (limited to 'content/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 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 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 -- cgit v1.2.3