/*-------------------------------------------------------------------------
 * 功能描述：DPAlgorithml
 * 作者：xulisong
 * 创建时间： 2019/1/31 10:08:02
 * 版本号：v1.0
 *  -------------------------------------------------------------------------*/

using FWindSoft.Data.Graph;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Test
{
    /*
     * 动态规划问题的特点，是递推
     */
    /// <summary>
    /// 步数集合
    /// </summary>
    public class StepSet : List<string>
    {
        public StepSet()
        {

        }
        public StepSet(List<string> list) : base(list)
        {
           
        }
    }
    public class DPAlgorithml
    {
        public static List<StepSet> GetStepSet1()
        {
            return new List<StepSet>() {new StepSet() {"1"}};
        }

        public static List<StepSet> GetStepSet2()
        {
            return new List<StepSet>() { new StepSet() { "1","1" },new StepSet(){"2"} };
        }

        public static List<StepSet> GetSetpSet(int stepNum)
        {
            var result= new List<StepSet>();
            if (stepNum < 0)
                return result;
            if (stepNum == 1)
            {
                return GetStepSet1();
            }
            if (stepNum == 2)
            {
                return GetStepSet2();
            }
            var set1= GetSetpSet(stepNum - 1);
            var set2 = GetSetpSet(stepNum - 2);
            set1.ForEach(s => s.Add("1"));
            set2.ForEach(s => s.Add("2"));
            result.AddRange(set1);
            result.AddRange(set2);
            return result;
        }

        private static List<StepSet> Clone(List<StepSet> sets,string step="1")
        {
            //集合的映射处理比直接递归还要费时间
            //new List<StepSet>(sets);//
            return  sets.Select(s =>
            {
                var set= new StepSet(s);
                set.Add(step);
                return set;
            }).ToList();
        }
        public static List<StepSet> GetSetpSet2(int stepNum)
        {
            var result = new List<StepSet>();
            if (stepNum < 0)
                return result;
            var backTwo = GetStepSet1();
            var backOne = GetStepSet2();
            if (stepNum == 1)
            {
                return backTwo;
            }
            if (stepNum == 2)
            {
                return backOne;
            }
            for (int i = 3; i <= stepNum; i++)
            {
                var temp = backOne;// new List<StepSet>(backOne);
                var set1 = Clone(backOne,"1");
                var set2 = backTwo;// Clone(backTwo);
               // set1.ForEach(s => s.Add("1"));
                set2.ForEach(s => s.Add("2"));
                backOne = set1;// new List<StepSet>(set1);
                backOne.AddRange(set2);
                backTwo = temp;
            }
            return backOne;
        }
    }
    #region 问题描述

    public class DPAlgorithml1
    {
        #region 描述
        /*
         * 面值为（1,3,5）的纸币，用最小的张数凑出11
         */
        #endregion
        public static List<string> GetSouluction(List<int> source, int count)
        {
            var reuslt = CreateSource(source);
         
            return GetSouluction(reuslt,source,count);
        }
        public  static Dictionary<int, List<string>> CreateSource(List<int> source)
        {
            Dictionary<int, List<string>> dic = new Dictionary<int, List<string>>();
            foreach (var item in source)
            {
                dic[item] = new List<string>() { item.ToString() };
            }
          
            return dic;
        }
        private static List<string> GetSouluction(Dictionary<int,List<string>> resultCache,List<int> source,int count)
        {
            if (resultCache.TryGetValue(count,out List<string> re))
            {
                return new List<string>(re);
            }
            List<string> result =null;
            int useCount = int.MaxValue;
            foreach (var step in source)
            {
                if (count > step)
                {
                    var tempResult = GetSouluction(resultCache,source, count - step);
                    tempResult.Add(step.ToString());
                    if (tempResult.Count < useCount)
                    {
                        result = tempResult;
                        useCount = tempResult.Count;
                    }
                }
            }
            result= new List<string>(result ?? new List<string>());
            resultCache[count] = new List<string>(result);
            return result;
        }
    }
    #endregion
    #region 问题描述

    public class DPAlgorithml2
    {
        #region 描述
        /*
         *体积价值二维关系(4,7),(2,3),(5,9)
         */
        #endregion

        
     
    }
    #endregion

    public static class TestDijlstra
    {
        public static string Test()
        {
            SimpleEdgeGraph graph = new SimpleEdgeGraph();
            graph.AddEdge("A", "B", 5);
            graph.AddEdge("A", "C", 2);
            graph.AddEdge("B", "D", 1);
            graph.AddEdge("C", "D", 6);
            graph.AddEdge("B", "E", 6);
            graph.AddEdge("D", "E", 1);
            graph.AddEdge("D", "F", 2);
            graph.AddEdge("E", "G", 7);
            graph.AddEdge("F", "G", 3);
            var results = GraphUtils.Dijkstra(graph, "A");
            StringBuilder builder = new StringBuilder();
            foreach (var result in results)
            {
                builder.AppendFormat("path:{0}  weight:{1}", string.Join(",", result), result.Weight);
                builder.AppendLine();
            }
            File.WriteAllText(@"d:\dijkstra.txt", builder.ToString());
            return builder.ToString();
        }
    }
    public static class TestFloyd
    {
        public static string Test()
        {
            SimpleEdgeGraph graph = new SimpleEdgeGraph() { IsDirection = true };
            graph.AddEdge("1", "4",4);
            graph.AddEdge("1", "2", 2);
            graph.AddEdge("4", "3", 12);
            graph.AddEdge("4", "1", 5);
            graph.AddEdge("3", "4", 1);
            graph.AddEdge("3", "1", 17);
            graph.AddEdge("2", "3", 3);
            graph.AddEdge("1", "3", 6);
            var results = GraphUtils.Floyd(graph);
            StringBuilder builder = new StringBuilder();
            foreach (var result in results)
            {
                builder.AppendFormat("path:{0}  weight:{1}", string.Join(",", result), result.Weight);
                builder.AppendLine();
            }
            File.WriteAllText(@"d:\dijkstra.txt", builder.ToString());
            return builder.ToString();
        }
    }
}