创意网站建设策划方案,智能在线设计平台,哪种语言做的网站好,wordpress 分类 标题前言
动态规划是大家都熟悉与陌生的知识#xff0c;非常灵活多变#xff0c;我自己也不敢说自己掌握了#xff0c;今天给大家介绍一道题#xff0c;不仅局限于动态规划做题#xff0c;还会上升到信息论#xff0c;乃至于启发自己认知世界的角度 因为比较难#xff0c;本…前言
动态规划是大家都熟悉与陌生的知识非常灵活多变我自己也不敢说自己掌握了今天给大家介绍一道题不仅局限于动态规划做题还会上升到信息论乃至于启发自己认知世界的角度 因为比较难本文不会详细介绍动态规划方法所以需要读者有一定基础否则可能理解有困难
题目链接可怜的小猪
有 buckets 桶液体其中 正好有一桶 含有毒药其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药你可以喂一些猪喝通过观察猪是否会死进行判断。不幸的是你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下
选择若干活猪进行喂养可以允许小猪同时饮用任意数量的桶中的水并且该过程不需要时间。小猪喝完水后必须有 minutesToDie 分钟的冷却时间。在这段时间里你只能观察而不允许继续喂猪。过了 minutesToDie 分钟后所有喝到毒药的猪都会死去其他所有猪都会活下来。重复这一过程直到时间用完。
给你桶的数目 buckets minutesToDie 和 minutesToTest 返回 在规定时间内判断哪个桶有毒所需的 最小 猪数 。
示例 1
输入 buckets 1000, minutesToDie 15, minutesToTest 60
输出 5示例 2
输入 buckets 4, minutesToDie 15, minutesToTest 15
输出 2示例 3
输入 buckets 4, minutesToDie 15, minutesToTest 30
输出 2dp解析
一般来说动态规划就是三步骤
定义数组含义多数情况是int值 dp[]或者dp[][]赋予初始值找到状态转移方程开始递推
推到最后大部分情况下dp数组最后一个值就是答案
这个题
题中有buckets,minutesToTest,minutesToDie三个变量由于正面角度比较难思考可以反过来 全问题为n只小猪能够有限的轮次测试中测出毒药一轮耗时minutesToDie总轮数为minutesToTest/minutesToDie
所以其子问题为i只小猪测试j轮的结果不影响后续测试而后续测试需要子问题的结果来递推 满足动态规划的重叠子问题和无后效性原则同时又是求最值简称n)所以确定可以用动态规划简称dp)
首先定义数组含义 f(i, j)表示i只小猪测试j轮后最多可以在多少butkets中找到毒药显然这是一个二维数组dp[i][j]然后赋予初始值 dp[0][0] dp[i][0]都为1相当于没有测试因为知道必有一桶毒所以bucket 1时可以肯定为有毒dp[0][j]没有猪也全为1状态转移 假设现在状态要算f(i, j)一轮测试后还剩下k只猪存活而测试剩下j - 1次可以确定f(k, j - 1)就是f(i, j )的前一个状态并将递推出f(i, j) 从i变为k的可能组合数为 C(i, k)因此f(i, j) C(i, k) * f(k, j - 1)其中k的取值为0~i所以最后的计算如下 f ( i , j ) ∑ k 0 i f ( k , j − 1 ) × C i k f(i,j) \sum_{k0}^i f(k, j-1) \times C_{i}^{k} f(i,j)k0∑if(k,j−1)×Cik
到了这步已经掌握了解题钥匙更多细节可以参考题解 本文并非想详细介绍题解更多的是探讨思想
信息论
抛开dp的过程只看开始和结尾buckets,minutesToTest,minutesToDie都限定后通过递推或者某种方式我们就能得到最少的猪数量n也就是说当相关信息量确认好后答案就确定了
这给我们一个很大提示那就是面对一个问题的时候在耗费时间去做之前仅仅凭借已经掌握的信息就能判断出能不做成。注意这里不是靠经验或者直觉而是真真实实的科学若是吸收这一思想并勤加练习相当多的难题可以得到解决
那现在我们就来仔细了解下这一理论吧
我们知道计算机的很多数据看不见摸不着我们将其统一设置为二进制使用bit来记录数据创造纷繁的信息世界。而我们不知道三维世界的造物主用的几进制在这个世界的我们无法用自己的信息来精确表达信息本身
熵
不过没关系我们可以一个模糊的“熵”暂时代替表示混乱度越混乱熵越高 熵增定律在一个孤立系统里如果没有外力做功其总混乱度熵会不断增大 对于理科生很好理解毕竟学过 对于保洁也很好理解毕竟一个房间如果长期不打扫肯定会变脏 对于老师也很好理解毕竟他如果长时间不来教室教室肯定乱套 对于宅男更好理解长期不外出不和人交流一定……
信息熵与信息
在信息论中信息熵表示信息的不确定程度
比如我们都知道同样的内容中文写的往往比英文薄一些实际上就是因为中文的信息不确定程度高也就是信息熵大所以所需的信息量就会少字数也会少往往掌握1000个汉字就能应付日常说话很多汉字在不同的组词下有大量不同的含义。而英文掌握5000单词都未必能说清楚
但是信息熵大未必是好事信息熵越大不确定程度越高其实代表信息量越少而减少信息熵的方式就是增加含信息量的信息不含信息量的信息可以归类为废话说到这我都不认识信息两字了
所以方向来了对于一件富含信息熵的事情我只要掌握足够信息量的信息与信息熵等价那么就可以做
比如明天是否下雨这件事信息熵很大天气预报的结果天上的乌云蚂蚁搬家等等都是多多少少降低信息熵的信息
到了这里你可以还是会有疑惑说来说去最后不还是靠感觉吗不过是用了一些科学名词归类而已
香农厉害就厉害在这里讲一个千万年来人说不清的感觉提取出公式让人类的认知进入了一个全新领域。在信息论提出之后个人认为能与这一瞬间媲美的只有阿姆斯特朗的那一小步。 公式如下 H ( X ) − ∑ i 1 n p ( x i ) log b p ( x i ) H(X) -\sum_{i1}^n p(x_i)\log_b p(x_i) H(X)−i1∑np(xi)logbp(xi) 看起来挺复杂但是理解很简单
其中H(X)表示随机变量X的信息熵P(xi)表示X取值为xi的概率logb表示以b为底的对数。
这里的b表示信息单位的基础如果你想二进制表示那么b 2 x表示事件xi可以理解为x里面的某种元素公式就是将X事件中1~n种元素发生的概率求和而来n可以理解为可能的所有情况
比如扔一枚硬币只有两种情况那么其信息熵为 H ( X ) − ∑ i 1 2 p ( x i ) log 2 p ( x i ) − [ 0.5 log 2 ( 0.5 ) 0.5 log 2 ( 0.5 ) ] 1 b i t H(X) -\sum_{i1}^2 p(x_i)\log_2 p(x_i) -\left[0.5\log_2(0.5) 0.5\log_2(0.5)\right] 1 bit H(X)−i1∑2p(xi)log2p(xi)−[0.5log2(0.5)0.5log2(0.5)]1bit
也就是说只要有一个含1bit信息量的信息就可以消灭信息熵比如我告诉你硬币为正面此时信息熵消失
解题
回到小猪的话题题目充满了H(X)信息熵在minutesToTest,minutesToDie限定下,X为bucket数x为1000时 H − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) − . . . − ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) H - (1/1000) * log2(1/1000) - (1/1000) * log2(1/1000) - ... - (1/1000) * log2(1/1000) H−(1/1000)∗log2(1/1000)−(1/1000)∗log2(1/1000)−...−(1/1000)∗log2(1/1000) − 1000 ∗ ( 1 / 1000 ) ∗ l o g 2 ( 1 / 1000 ) l o g 2 ( 1000 ) ≈ 9.97 - 1000 * (1/1000) * log2(1/1000) log2(1000) ≈ 9.97 −1000∗(1/1000)∗log2(1/1000)log2(1000)≈9.97 我们可以对这个结果有些感性认识看起来信息熵的增长不是线性的而是log扔硬币这种五五开的事情为1而1000桶水找1个有毒居然只有9.97当有10000桶水时信息熵为log2(10000) 13.29
现在我们就要考虑多少小猪能提供超过9.97
参考链接https://www.zhihu.com/question/60227816/answer/1274071217 https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
