《背包九讲》

P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。 基本思路 这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”;如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 注意f[i][v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[i][v-1],这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以,由你自己来体会了。 优化空间复杂度 以上方法的时间和空间复杂度均为O(N*V),其中时间复杂度基本已经不能再优化了,但空间复杂度却可以优化到O(V)。 先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f [0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v -c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i -1][v-c[i]]的值。伪代码如下: for i=1..N for v=V..0 f[v]=max{f[v],f[v-c[i]]+w[i]}; 其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。 总结 01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。 P02: 完全背包问题 题目…

0 Comments

深度信念网络的入门

写在前面,菜鸟上路。 [mathJax] 由于项目需要,接触了深度学习这个坑,在此记录一下自己的学习过程。 1.rbm结构 首先学的是深度信念网络(dbn)这个略显简单的网络。dbn主要结构是由rbm和bp网络构成的。下面我们从rbm开始我们的探索之旅。 rbm(restricted Boltzmann machine, RBM)的中文名字是受限玻尔兹曼机。这是一种可以通过输入数据集学习概率分布的随机生成神经网络。之所以被叫做受限是这个模型限定为二分图(二分图可以看我这篇博客的解释。这一限定使得相比一般玻兹曼机更高效的训练算法成为可能,特别是基于梯度的对比分歧(contrastive divergence)算法。 接下来,我们看一下rbm的网络结构。rbm由两层神经元组成。一层是可见层(v,偏置为a。一层是隐藏层(h,偏置为b。其中常用的rbm神经元取值是二值的,即0或1。可见层和隐藏层是全连接的,其中权重系数是W。 在这个定义里面,每个单元的能量是 $$ E(v, h)=-sum_{i} a_{i} v_{i}-sum_{j} b_{j} h_{j}-sum_{i} sum_{j} h_{j} w_{i, j} v_{i} $$ 隐藏层与可见层的联合概率分布可以用下面的函数表示: $$Z=sum_{节点的所有可能取值} e^{-E(v,h)}$$ $$P(v,h)=frac{1}{Z}  e^{-E(v,h)}$$…

0 Comments

3 sum closest

在黑暗中找到光,藏在孤星之中也会找的到你。 问题描述:给定n个整数和一个目标整数。找到在这n个整数中满足三个数之和最接近目标数的三个数,返回这三个数的和。 注意:假设每一个输入都只有一个唯一的解。n个整数用一个数组存储。 限制:3 <= nums.length <= 10^3      -10^3 <= nums[i] <= 10^3       -10^4 <= target <= 10^4 解题思路:最直观的想法就是遍历这个数组中的所有的三个数之和。将每个三个数之和与目标数相减得到一个中间值作为衡量接近程度的指标。通过循环遍历所有的三个数之和,将中间值最小的作为判断是否找到最邻近数的标准。找到后,返回三个数之和。 具体步骤:先将数组中的前三个数的和做为基准值1,与目标数相减作为基准值2。假设基准值1就是我们要找的返回值。通过将所有的三数之和与目标数相减的值与基准值2作比较,当这个值比基准值2小的时候,基准值1更新为当前三数之和,基准值2更新为当前相减的值。最后返回更新迭代后的基准值1。比较的时候可以使用abs函数。 代码: #include<math.h> int threeSumClosest(int* nums,…

0 Comments

回文数(Parlindrome)

和光同尘 回文数是这样的数,即一个数从左往右数和从右往左数是同样的结果。比如aba,121. leetcode有一道题就是判断一个数是否是回文数。 问题描述:给定一个整数(int 类型),如果是回文数,函数返回为true. bool isPalindrome(int x){ } 1.自然的想到将数字转为字符,利用python中的字符翻转读取然后与原字符进行判断。str(x)==str(x)[:-1] 2.如果不能使用字符的话。可以考虑对数字进行翻转,对整个数字翻转可能会超界。因此可以考虑对数字的一半进行翻转。如何判断到了数字的一半呢?不妨设我们翻转的数为rev. while(x>rev) { rev=rev*10+x%10; x/=10; } 如上,当rev>x的时候,rev有和原数一半的位数或者一半的位数多一位。因此当rev/10或者rev和x(原数x的前一半)相等时,该数x是回文数。同时,当x是负数的时候,该数显然不为回文数。最后代码如下: bool isPalindrome(int x){ int rev=0; if(x<0||(x%10==0&&x!=0)) { return false; } while(x>rev) { rev=rev*10+x%10;…

0 Comments