专栏首页大猪的笔记C#笔记:动态规划算法

C#笔记:动态规划算法

一个复杂的问题,通常逐级会分解成一系列小问题。而且很多情况下,某些小问题是相似的。但是使用传统的递归,会将相同相似的小问题进行重复的计算。这样浪费了算力。 所谓动态规划算法,实质是使用一个表,记录下所有小问题的值。如果在计算中再次遇到相同问题,则直接取值。不做计算。显然,如果每个小问题都是不同的,那么此算法没有优势。 比如斐波那契数列,就是一个简单的例子。 定义:

Fab(n)= Fab(n-1)+Fab(n-2)
Fab(1)=Fab(2)=1;

实现1:

static int GetFab(int n)
        {
            if (n == 1) return 1;
            if (n == 2) return 1;
            return GetFab(n - 1) + GetFab(n - 2);
        }

假如我们求Fab(5) 。那我们需要求Fab(4) +Fab(3)。 Fab(4)=Fab(3)+Fab(2).....显然。 Fab(3)被计算机不加区别的计算了两次。而且随着数字的增大,计算量是指数增长的。 如果我们使用一个数组,记录下Fab的值。当Fab(n)!=null 时。直接读取。那么,我们就能把时间复杂度控制在 n 以内。 实现2:

static int[] fab = new int[6];
static int GetFabDynamic(int n)
        {
            if (n == 1) return fab[1] = 1;
            if (n == 2) return fab[2] = 1;
            if (fab[n] != 0)//如果存在,就直接返回。
            {
                return fab[n];
            }
            else //如果不存在,就进入递归,并且记录下求得的值。
            {
                return fab[n] = GetFabDynamic(n - 1) + GetFabDynamic(n - 2);
            }
        }

这就是,动态规划算法的 备忘录模式。只需要把原来的递归稍微修改就行了。 下面是0-1背包问题的解法。可以对比一下。(一个限重w的背包,有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值) 

static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分别为3, 4, 7, 8, 9 且是不可分割的  0-1 背包问题
        static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的价值分别为4, 5, 10, 11, 13
        static int capacity = 16;
        static int[,] dp = new int[6, capacity + 1];
        static int knapsack(int n, int w)
        {
            if (w < 0) return -10000;
            if (n == 0) return 0;
            if (dp[n, w] != 0)
            {
                return dp[n, w];
            }
            else
            {
                return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) + values[n - 1]);
                  /*                 
                 * knapsack(n,w) 指在前N件物品在W剩余容量下的最大价值。
                 * 这个公式的意思是,对于某一件物品,
                 * 1、如果选择装进去,那么,当前价值=前面的n-1件物品在空位w - size(n)下的最大价值(因为空位需要留出,空位也隐含了价值)。
                 * 再加上这件物品的价值。等于 knapsack(n - 1, w - size[n - 1]) + values[n - 1]
                 * 2、 如果我们选择不装进去,那么,在n-1物品的情况下空位仍然在,当前价值 = 前面n-1件物品在空位w下的最大价值。
                 * 等于knapsack(n - 1, w)
                 * 注意:随着演算,某一情况下的价值不会一成不变。
                 * 此时我们做出决策:到底是在装入时的价值大,还是不装入时的价值大呢?我们选择上面两种情况中值较大的。并记录在案。
                 * 最后dp[N,M]就是我们要求的值。
                 */            }
        }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • python笔记:时间,排序

    在应用中,应该尽可能使用utc time。 time.time()产生的timestamp是utc为基准的。不包含时区信息。 或者使用:datetime.d...

    超级大猪
  • C#笔记:RC6算法实现

    超级大猪
  • python: 使用http方式调用pb协议

    超级大猪
  • Java每日一练(2017/8/23)

    最新通知 ●回复"每日一练"获取以前的题目! ●【新】Android视频更新了!(回复【安卓视频】获取下载链接) ●【新】Ajax知识点视频更新了!(回复【学习...

    Java学习
  • BZOJ 1597: [Usaco2008 Mar]土地购买【斜率优化+凸包维护】

    1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 4989 ...

    Angel_Kitty
  • 优化 Java 中的多态代码

    Oracle的Java是一个门快速的语言,有时候它可以和C++一样快。编写Java代码时,我们通常使用接口、继承或者包装类(wrapper class)来实现多...

    用户1257393
  • 代码小目

    标签: 代码片段 日常记录 日常记录的代码片段 1.使用Paralle进行并行计算累加求和的不同形式 public static int ParallelSum...

    潘成涛
  • P1514 引水入城

    题目描述 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个N 行M 列的矩形,如上图所示,其中每个格子都代...

    attack
  • Java面试-List中的sort详细解读

    最近看了一些排序相关的文章,因此比较好奇,Java中的排序是如何做的。本篇文章介绍的是JDK1.8,List中的sort方法。

    健程之道
  • 应用对持久数据的管理 | 从开发角度看应用架构7

    当应用程序将数据存储在永久性存储中(例如flat file,XML文件或数据库的持久性数据)时,它被称为数据的持久性。 关系数据库是企业应用程序用来保存数据以供...

    魏新宇

扫码关注云+社区

领取腾讯云代金券