贪心算法之活动选择问题

因为有的问题，用动态规划解决起来，比较耗费性能，而用贪心算法，虽然不能得到最优解，但也能得到次优解，与动态规划比起来更加简单节约性能。

动态规划解决活动选择问题

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 贪心算法 { class Program { //动态规划 static void Main(string[] args) { int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; List<int>[,] result = new List<int>[13,13]; for(int i=0;i<13;i++) { for(int j = 0;j < 13;j++) { result[i, j] = new List<int>(); } } for(int j=0;j<f.Length;j++) { for(int i=0;i<j;i++) { List<int> Sij = new List<int>(); for(int k = 0;k<f.Length;k++) { if(f[i]<=s[k]&&f[k]<=s[j]) { Sij.Add(k); } } if(Sij.Count>0) { int maxCount = 0; List<int> tempList = new List<int>(); foreach (int k in Sij) { int count = result[i, k].Count + result[k, j].Count + 1; if(count >maxCount) { maxCount = count; tempList = result[i, k].Union<int>(result[k, j]).ToList<int>(); tempList.Add(k); } } result[i, j] = tempList; } } } foreach (int temp in result[0,12]) { Console.WriteLine(temp); } Console.ReadKey(); } } }

贪心算法-递归迭代来实现

通常最早结束的活动a1它一定在最优解中，根据这一点来实现贪心算法。

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 贪心算法_递归代码实现 { class Program { static void Main(string[] args) { List<int> result = Methord(0, 11, 0,24); foreach (int temp in result) { Console.WriteLine(temp); } Console.ReadKey(); List<int> result2 = Methord2(0, 11, 0, 0); foreach (int item in result2) { Console.WriteLine(item); } Console.ReadKey(); } static int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; static int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; // static List<int> result = new List<int>(); /// <summary> /// /// </summary> /// <param name="startActiveNum"></param>开始活动的编号 0 /// <param name="endActiveNum"></param>结束活动的编号 n /// <param name="startTime"></param>开始活动的时间 上一个活动 0 /// <param name="endTime"></param>结束活动的时间 总活动时间 /// <returns></returns> static List<int> Methord(int startActiveNum,int endActiveNum,int startTime,int endTime) { if(startActiveNum>endActiveNum) { return new List<int>(); } int temp = 0; //从下一个活动开始 for(int number = startActiveNum;number<=endActiveNum;number++) { if(s[number]>=startTime&&f[number]<=endTime) { // result.Add(number); temp = number; break; } } List<int> list = Methord(temp+1, endActiveNum, f[temp],endTime); list.Add(temp); return list; } /// <summary> /// /// </summary> /// <param name="startActiveNum"></param>上一个活动那个的开始时间 /// <param name="endActiveNum"></param> 最后一个活动的编号通常是一个定值 /// <param name="startTime"></param> 上一个活动的开始时间 /// <param name="endTime"></param> 上一个活动的结束时间 /// <returns></returns> static List<int> Methord2(int startActiveNum, int endActiveNum, int startTime, int endTime) { if (startActiveNum > endActiveNum) { return new List<int>(); } int temp = 0; //从下一个活动开始 for (int number = startActiveNum; number <= endActiveNum; number++) { if (s[number] >= endTime) { // result.Add(number); temp = number; break; } } List<int> list = Methord2(temp + 1, endActiveNum, s[temp], f[temp]); list.Add(temp); return list; } } }

贪心算法通过迭代实现（for循环）

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 贪心算法_活动选择_迭代代码 { class Program { static void Main(string[] args) { int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; int startTime = 0; int endTime = 24; List<int> list = new List<int>(); for(int number = startTime;number<12;number++) { if(s[number]>=startTime&&f[number]<endTime) { list.Add(number); startTime = f[number]; } } foreach (int item in list) { Console.WriteLine(item); } Console.ReadKey(); } } }

贪心算法——钱币找零问题

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 贪心算法_钱币找零问题 { class Program { static void Main(string[] args) { int[] value = { 1, 2, 5, 10, 20, 50, 100 }; int[] count = { 3, 0, 2, 1, 0, 3, 5 }; int[] result = Methord(150, value, count); foreach (int item in result) { Console.Write(item + " "); } Console.ReadKey(); } static int[] Methord(int k,int []value,int []count) { int[] result = new int[value.Length+1] ; int index = value.Length - 1; while(true) { if(k<=0||index<0) { break; } if(k>count[index]*value[index]) { k -= count[index] * value[index]; result[index] = count[index]; } else { result[index] = k / value[index]; k -= value[index] * result[index]; } index--; } result[count.Length] = k; return result; } } }