算法洗脑系列(8篇)——第七篇 动态规划-阿里云开发者社区

开发者社区> 一线码农> 正文

算法洗脑系列(8篇)——第七篇 动态规划

简介:
+关注继续查看

     今天跟大家分享下算法思想中比较难的一种"动态规划",动态规划给人像是作战时常用的“迂回战术”,或者说是

游击战,在运动中寻找突破口。

 

一: 思想

   首先要了解”动态规划“,必须先知道什么叫做”多阶段决策“,百科里面对这个问题解释的很全,我就load一段出来,

大家得要好好品味,好好分析。

 

上面图中最后一句话就定义了动态规划是要干什么的问题。

 

二:使用规则

    现在我们知道动态规划要解决啥问题了,那么什么情况下我们该使用动态规划呢?

   ①  最优化原理(最优子结构性质):

           如果一个问题的最优策略它的子问题的策略也是最优的,则称该问题具有“最优子结构性质”。

   ②  无后效性:

           当一个问题被划分为多个决策阶段,那么前一个阶段的策略不会受到后一个阶段所做出策略的影响。

   ③  子问题的重叠性:

          这个性质揭露了动态规划的本质,解决冗余问题,重复的子问题我们可以记录下来供后阶段决策时

        直接使用,从而降低算法复杂度。

 

三:求解步骤

      ①   描述最优解模型。

      ②   递归的定义最优解,也就是构造动态规划方程。

      ③   自底向上的计算最优解。

      ④   最后根据计算的最优值得出问题的最佳策略。

 

四:与其他算法的差异

     ① 递归:  递归采用的是“由上而下”的解题策略并带有可能的”子问题“重复调用,时间复杂度自然高。

                   而”动态规划“采用”自下而上“并带有临时存储器保存上一策略的最优解,空间换时间。

     ② 分治:  同样两者都是将问题划分为很多的子问题,不同的是”动态规划“中各子问题是相互联系的。

     ③ 贪心:  要注意的是贪心算法每走一步都是不可撤回的,而动态规划是在一个问题的多种策略中寻找

                   最优策略,所以动态规划中前一种策略可能会被后一种策略推翻。

 

五:举例

  动态规划中,最经典最著名的例子莫过于”背包问题“,现有:

    苹果: 1kg    12¥

    梨子: 1kg     3¥

    葡萄: 1kg    10¥

    板栗: 1kg    25¥  

现有一个背包,只能装3kg水果,那么如何得到物品价值最大化?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BeiBao
{
    public class Program
    {
        static void Main(string[] args)
        {
            Goods goods = new Goods()
            {
                LimitWeight = 3,
                LimitNum = 4,
                Weight = new double[4] { 1, 1, 1, 1 },
                Value = new double[4] { 12, 3, 10, 25 }
            };

            BackPack(goods, 0, 0, goods.Value.Sum());

            Console.WriteLine("经过最优化求解:\n");

            for (int i = 0; i < goods.Selected.Length; i++)
            {
                if (goods.Selected[i])
                {
                    Console.WriteLine("重量:" + goods.Weight[i] + " 价值:" + goods.Value[i]);
                }
            }

            Console.Read();
        }

        static double maxValue;

        static bool[] selected = new bool[4];

        static void BackPack(Goods good, int i, double tw, double tv)
        {
            //当前追加物品的重量
            var currentWeight = tw + good.Weight[i];

            //当前重量小于限制重量则继续追加
            if (currentWeight <= good.LimitWeight)
            {
                selected[i] = true;

                //如果当前不是最后一个商品,则继续追加
                if (i < good.LimitNum - 1)
                {
                    BackPack(good, i + 1, tw + good.Weight[i], tv);
                }
                else
                {
                    for (int k = 0; k < good.LimitNum; k++)
                    {
                        good.Selected[k] = selected[k];
                    }
                    maxValue = tv;
                }
            }

            selected[i] = false;

            //这里就体现了动态规划的根本目的,解决冗余
            if (tv - good.Value[i] > maxValue)
            {
                if (i < good.LimitNum - 1)
                {
                    //排除当前物品所剩余的价值总值
                    var exceptNotSelectedValue = tv - good.Value[i];

                    BackPack(good, i + 1, tw, exceptNotSelectedValue);
                }
                else
                {
                    for (int k = 0; k < good.LimitNum; k++)
                    {
                        good.Selected[k] = selected[k];
                    }

                    maxValue = tv - good.Value[i];
                }
            }
        }
    }

    #region 商品的实体
    /// <summary>
    /// 商品的实体
    /// </summary>
    public class Goods
    {
        public double[] Value = new double[4];
        public double[] Weight = new double[4];
        public bool[] Selected = new bool[4];
        public int LimitNum { get; set; }
        public double LimitWeight { get; set; }
    }
    #endregion
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
4029 0
leetcode算法题解(Java版)-15-动态规划(斐波那契)
两种思路,都是递归。第一种是递归的判断每个节点的左右子树的深度是否只相差一以内。第二种做了剪枝处理,当判断到一个子树已经不满足时就返回结果。
2099 0
算法学习之路|动态规划简单入门
动态规划简单入门:以最长递增子序列等举例
1738 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
3971 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
7616 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
10745 0
算法起步之动态规划LCS
原文: 算法起步之动态规划LCS             前一篇文章我们了解了什么是动态规划问题,这里我们再来看动态规划另一个经典问题,最长公共子序列问题(LCS),什么是子序列,我们定义:一个给定序列将其中的0个或者多个元素去掉之后得到的序列就是他的子序列。
905 0
+关注
194
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载