C# 算法系列 - 贪婪算法（动态规划问题）

using System;
using System.Collections.Generic;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            /*===========贪婪算法(动态规划问题)==============
                钢条切割问题
                某公司出售钢条，出售价格与钢条长度之间的关系如下表：
                长度i（米）  1    2   3   4   5   6   7   8   9   10
                价格p（元）  1    5   8   9   10  17  17  20  24  30    

                问题：现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使得总收益最大。
                举个栗子，下面列出的是0-10的最优收益
                    长度（米）  0    1    2   3    4    5    6    7   8    9   10 
                最大利益（元）  0    1    5   8   10   13   17   18   22   25  30 

                说明：长度1的时候不用切就是1,
                      长度2的时候可以切1+1，可以不切5，得到5，
                      长度3的时候，首先不切是8，切1和2，2还可以切，但是2其实我们之前已经切过了，最优是5，
                      所以不用继续考虑了，1和2就是1+5=6，最优是8，
                      直接看长度8的时候，可以不切20，可以切1和7,7之前也考虑过了是17，
                      所以1和7就是1+18=19，最后发现最优是2和6，也就是5+17=22。
             */
            int[] it = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            for (int i = 0; i < it.Length; i++)
            {
                Console.WriteLine($"长度为 {i} 米的钢条，切割后，最大收益是 {GetCutMaxValue(i)} 元");
            }
            Console.ReadKey();
        }


        //自底向上
        public static int GetCutMaxValue(int n)
        {
            int[] P = new int[] { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };//价格表
            List<int> r = new List<int>();//还是需要一个列表存子问题
            r.Add(0);//0长度收益0
            for (int i = 1; i < n + 1; i++)//自底向上从1开始存子问题
            {
                //每次需要重新计算收益
                int res = 0;
                //利用的是简化的递推式2，对于这个循环i就是n,j就是i
                for (int j = 1; j < i + 1; j++)
                {
                    //本来r[i-j]也就是n-1，是需要递归，但是因为我们已经存过了，直接取就好了
                    res = Math.Max(res, P[j] + r[i - j]);
                }
                r.Add(res);
            }
            return r[n];
        }
    }
}

MSCL超级工具类库
基于C#开发的超强工具类，包含数据库操作，字符串处理，文件或者文件夹处理
网络请求，缓存处理，数据容器等上百个常用工具类封装，附带调用示例和参数说明，
提供CHM详细文档，上百个生产环境使用，稳定高效，简单易用。
真正做到“工具在手，一切尽有”，让你大幅度的提高编程效率，提高编程水平。
联系QQ：7400799（请备注 "MSCL"）

===============================================

重要压缩文件忘记解压密码？网上下载rar/zip/7z等压缩文件，需要密码？
====极速解密助手，支持支持RAR/ZIP/7Z等多种压缩文档解密======
★ 解密不超过24小时，跟密码复杂程度相关
★ 解密成功后再收费，无套路
★ 解密成功后自动删除原件，无后顾之忧
联系QQ：7400799（请备注 "文件解密"）

==============================================

Magic.Orm已在数百个成熟项目中应用，是比较完善的ORM框架（基于C#开发）。开发过程中参考了NBear与MySoft，吸取了其中的一些精华，加入新思想，
后期参考EF的Lambda语法进行大量扩展。

为什么选择Magic.Orm?

• 上手简单，0学习成本。使用方便，按照sql书写习惯编写C#.NET代码。功能强大。
• 高性能，接近手写Sql。
• 体积小（不到200kb，仅一个dll）。
• 完美支持Sql Server(2000至最新版),MySql,Oracle,Access,Sqlite等数据库。
• 支持大量Lambda表达式写法。
• 不需要像NHibernate的XML配置，不需要像EF的各种数据库连接驱动，集成简单。

购买源码 请联系QQ：7400799（请备注 "ORM"）