From 2749e059084b99737d79aadd92521023b0f65f56 Mon Sep 17 00:00:00 2001 From: chai Date: Thu, 24 Jun 2021 16:41:21 +0800 Subject: *dp --- Assets/Algorithms/Recursion/Recursion_DC.cs | 144 +++++++++++++++++++++++ Assets/Algorithms/Recursion/Recursion_DC.cs.meta | 11 ++ Assets/Algorithms/Recursion/Recursion_DP.cs | 106 +++++++++++++++++ Assets/Algorithms/Recursion/Recursion_DP.cs.meta | 11 ++ 4 files changed, 272 insertions(+) create mode 100644 Assets/Algorithms/Recursion/Recursion_DC.cs create mode 100644 Assets/Algorithms/Recursion/Recursion_DC.cs.meta create mode 100644 Assets/Algorithms/Recursion/Recursion_DP.cs create mode 100644 Assets/Algorithms/Recursion/Recursion_DP.cs.meta diff --git a/Assets/Algorithms/Recursion/Recursion_DC.cs b/Assets/Algorithms/Recursion/Recursion_DC.cs new file mode 100644 index 0000000..7dc873d --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DC.cs @@ -0,0 +1,144 @@ +using System; +using System.Collections; +using System.Collections.Generic; +using AlgorithmCollection; +using UnityEngine; + +// 分治算法 +namespace AlgorithmCollection.Recursion +{ + + public static partial class RecursionHelper + { + + #region 分治框架 + public delegate DivisionDescriptor Init(); + public delegate void Solve(DivisionDescriptor division); + public delegate bool Divide(DivisionDescriptor division, out DivisionDescriptor[] divs);//返回值代表是否达到最小问题阈值 + public delegate void Merge(DivisionDescriptor[] divisions); + public delegate void Postprocess(DivisionDescriptor div); + + // 分治算法框架 + public static void DC(Init init, Divide divide, Solve solve, Postprocess postprocess = null, Merge merge = null) + { + DivisionDescriptor div = init(); + _DivideAndConquer(div, solve, divide, merge, postprocess); + } + + // 处理单个任务 + private static void _DivideAndConquer(DivisionDescriptor div, Solve solve, Divide divide, Merge merge, Postprocess postprocess) + { + DivisionDescriptor[] division; + bool bUnit = divide(div, out division); + if (!bUnit) + { + for (int i = 0; i < division.Length; ++i) + { + _DivideAndConquer(division[i], solve, divide, merge, postprocess); + postprocess?.Invoke(division[i]); + } + merge?.Invoke(division); + } + else + { + for (int i = 0; i < division.Length; ++i) + { + solve(division[i]); + } + } + } + #endregion + + #region 全排列，返回数据的所有组合 + public static void Permutations(List dataList, ref List> perms) + { + List> outPerms = new List>(); // A B C D + List temp = new List(dataList.Count); // + A (BCD) + DC( // + B (CD) + () => // init // + C(D) + { // +D + DivisionDescriptor div = new DivisionDescriptor(); // + D(C) + div.userdata = -1; // +C + div.left = 0; // + C (BD) + div.right = dataList.Count - 1; // + B(D) + return div; // + D(B) + }, // + D (BC) + (DivisionDescriptor div, out DivisionDescriptor[] divs) => // 划分 // + B(C) + { // + C(B) + int left = div.left; // 包含第一个元素在内的范围 // + B (ACD) + int right = div.right; // + C (ABD) + int pivot = (int)div.userdata; // 第一个元素在范围内的索引 // + D (ABC) + int l = left; + if (pivot != -1) + { + temp.Add(dataList[pivot]); + Algorithms.Swap(ref dataList, pivot, left); + l = left + 1; + } + divs = new DivisionDescriptor[right - l + 1]; + int j = 0; + for (int i = l; i <= right; ++i) + { + divs[j].left = l; + divs[j].right = right; + divs[j].userdata = (int)i; + j++; + } + return l == right; + }, + (DivisionDescriptor div) => // solve 最小子任务处理 + { + temp.Add(dataList[div.left]); + List newCompose = new List(temp); + outPerms.Add(newCompose); + temp.RemoveAt(temp.Count - 1); + }, + (DivisionDescriptor div) => //子任务后处理 + { + int pivot = (int)div.userdata; // 第一个元素的索引 + int left = div.left; + int right = div.right; + Algorithms.Swap(ref dataList, pivot, left); + temp.RemoveAt(temp.Count - 1); + } + ); + perms = outPerms; + } + + // 生成器形式，每次返回一个组合 + public static IEnumerable Permutations(List data) + { + foreach (var perm in _Permutations(data, 0, data.Count - 1)) + { + yield return perm; + } + } + + // 计算start~end范围内的全排列 + private static IEnumerable _Permutations(List data, int start, int end, List perm = null) + { + if (perm == null) + perm = new List(data.Count); + if (start == end) + { + perm.Add(data[start]); + yield return perm; + perm.RemoveAt(perm.Count - 1); + } + else + { + for (int i = start; i <= end; ++i) + { + perm.Add(data[i]); + Algorithms.Swap(ref data, start, i); + IEnumerator itor = _Permutations(data, start + 1, end, perm).GetEnumerator(); + while (itor.MoveNext()) + yield return itor.Current; + Algorithms.Swap(ref data, start, i); + perm.RemoveAt(perm.Count - 1); + } + } + } + #endregion + } +} \ No newline at end of file diff --git a/Assets/Algorithms/Recursion/Recursion_DC.cs.meta b/Assets/Algorithms/Recursion/Recursion_DC.cs.meta new file mode 100644 index 0000000..46827b2 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DC.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: 7f1f1be65b676ad46a43bd7515673e34 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs b/Assets/Algorithms/Recursion/Recursion_DP.cs new file mode 100644 index 0000000..a0205ba --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DP.cs @@ -0,0 +1,106 @@ +using System; +using System.Collections; +using System.Collections.Generic; +using AlgorithmCollection; +using UnityEngine; + +// 动态规划算法 +namespace AlgorithmCollection.Recursion +{ + + public static partial class RecursionHelper + { + //#region 动态规划框架 + //private static void DP() + //{ + + //} + //#endregion + + //最长公共子串 + // longest common subpart + public static void FindLCSP(T[] A, T[] B, ref List result) where T : IEquatable, IComparable + { + int end = 0; + int maxLen = 0; + int[,] dp = new int[A.Length, B.Length]; // 记录以A[i],B[j]结尾的子串的最长公共子串长度 + for(int i = 0; i < A.Length; ++i) + { // 1, A[i]==B[j] && (i==0 || j==0) + for (int j = 0; j < B.Length; ++j) //dp[i,j] = dp[i-1,j-1]+1, A[i]==B[j] && i!=0 && j!=0 + { // 0, A[i]!=B[j] + if(A[i].Equals(B[j])) + { + if (i == 0 || j == 0) // a b c b c e d + dp[i, j] = 1; // a 1 0 0 0 0 0 0 + else // c 0 0 1 0 1 0 0 + dp[i, j] = dp[i - 1, j - 1] + 1; // b 0 1 0 2 0 0 0 + if (maxLen < dp[i, j]) // c 0 0 2 0 3 0 0 + { // b 0 1 0 3 0 0 0 + maxLen = dp[i, j]; // c 0 0 2 0 4 0 0 + end = i; // e 0 0 0 0 0 5 0 + } // f 0 0 0 0 0 0 0 + } + } + } + if(maxLen > 0) + { + for (int i = 0; i < maxLen; ++i) + { + result.Add(A[end - maxLen + 1 + i]); + } + } + } + + //最长公共子序列 + // longest common subsequence + public static void FindLCSS(T[] A, T[] B, ref List result) where T : IEquatable, IComparable + { + int[,] dp = new int[A.Length, B.Length]; // 记录[0-i]和[0-j]两个子串的最长公共子序列长度 + int max = 0; + for (int i = 0; i < A.Length; ++i) // 1, A[i]==B[j] && (i==0 || j==0) + { //dp[i,j] = dp[i-1,j-1]+1, A[i]==B[j] && i!=0 && j!=0 + for(int j = 0; j < B.Length; ++j) // 0, A[i]!=B[j] && (i==0 || j==0) + { // max(dp[i,j-1],dp[i-1,j]), A[i]!=B[j] && i!=0 && j!=0 + if (A[i].Equals(B[j])) + { // a b c b c e d + if (i == 0 || j == 0) // a 1 1 1 1 1 1 1 + dp[i, j] = 1; // c 1 1 2 2 2 2 2 + else // b 1 2 2 3 3 3 3 + dp[i, j] = dp[i - 1, j - 1] + 1; // c 1 2 3 3 4 4 4 + if(max < dp[i, j]) // b 1 2 3 4 4 4 4 + { // c 1 2 3 4 5 5 5 + max = dp[i, j]; // e 1 2 3 4 5 6 6 + result.Add(A[i]); // f 1 2 3 4 5 6 6 + } + } + else + { + if (i == 0 || j == 0) + dp[i, j] = 0; + else + dp[i, j] = Algorithms.Max(dp[i - 1, j], dp[i, j - 1]); + } + } + } + Debug.Log(max); + } + + // 计算最大子段和 + public static int CalMaxSum(int[] nums) + { + int n = nums.Length; + int max = int.MinValue; + int sum = int.MinValue; //dp + for(int i = 0; i < n; ++i) + { + if (sum > 0) + sum += nums[i]; + else + sum = nums[i]; + max = Algorithms.Max(max, sum); + } + return max; + } + + } +} \ No newline at end of file diff --git a/Assets/Algorithms/Recursion/Recursion_DP.cs.meta b/Assets/Algorithms/Recursion/Recursion_DP.cs.meta new file mode 100644 index 0000000..fcaed18 --- /dev/null +++ b/Assets/Algorithms/Recursion/Recursion_DP.cs.meta @@ -0,0 +1,11 @@ +fileFormatVersion: 2 +guid: e5aefe863ec10ec41a87358acf61f595 +MonoImporter: + externalObjects: {} + serializedVersion: 2 + defaultReferences: [] + executionOrder: 0 + icon: {instanceID: 0} + userData: + assetBundleName: + assetBundleVariant: -- cgit v1.1-26-g67d0