GreenHatHGのBlog

部分背包，01背包，完全背包，多重背包 部分背包问题和01背包问题的区别就是：部分背包问题中的单个物品，可以取一部分装入背包。而0/1背包问题则是要么全部拿走，要么一无所有 完全背包与0-1背包问题的区别是：在0-1背包问题中，每个物品仅有一件；在完全背包问题中，每个物品有无限件 多重背包与完全背包问题的区别是：在完全背包问题中，每个物品有无限件；在多重背包问题中，每个物品有Mi件 混合背包问题相当于上面提到所有背包问题的混合：有的物品仅有1件，有的物品有无限件，有的物品有Mi件（有限件） 部分背包【部分背包】问题描述：n件物品，第i件物品价值 vi 元，重wi 磅。希望用 W磅的背包 拿走最重的物品。第i件物品可以都拿走，也可以拿走一部分。（物品可以分割所以称为部分背包） 因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。（1）先将单位块收益按从大到小进行排序；（2）初始化背包的剩余体积和当前价值；（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，剩余体积减去物品总体积；b.如果可以...

斐波那契兔子问题、斐波那契数－从爬楼梯问题、HDU2046 骨牌铺方格、ＨDU2044 一只小蜜蜂、HDU2048 神、上帝以及老天爷、HDU2049 不容易系列之(4)——考新郎、递推中的平面问题、HDU 2097 Children’s Queue、HDU2045 不容易系列之(3)—— LELE的RPG难题、HDU2047 阿牛的EOF牛肉、for beginner,HDU2563统计问题 递推的基本思想 首先确认，是否能很容易的得到简单情况的解 假设规模为N-1的情况已经得到解决 重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决 编程中的空间换时间的思想 并不一定是从N-1到N的分析 递推中的经典——Fibonacci sequence(斐波那契数列)先上递推中的fib数列的解题模板 1234567891011121314151617181920#include <isotream>#include <iostream>using namespace std;typedef long...

能被整除的那些事 能被2整除若一个整数的末位是0、2、4、6或8，则这个数能被2整除。 能被3整除若一个整数的数字和能被3整除，则这个整数能被3整除。 能被4整除若一个整数的末尾两位数能被4整除，则这个数能被4整除 能被5整除若一个整数的末位是0或5，则这个数能被5整除 能被6整除能被6整除的数的特征末尾是0、2、4、6、8且各位上数字的和能被3整除能被6整除的数的特征既要符合能被2整除的数的特征,又要符合能被3整除的数的特征 能被7整除若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。如果差太大或心算不易看出是否7的倍数，就需要继续上述「截尾、倍大、相减、验差」的过程，直到能清楚判断为止。例如，判断133是否7的倍数的过程如下：13－3×2＝7，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613－9×2＝595 ， 59－5×2＝49，所以6139是7的倍数，余类推。 能被8整除若一个整数的未尾三位数能被8整除，则这个数能被8整除 能被9整除若一个整数的数字和能被9整除，则这个整数能被9整除 能被10...

uva156 codeforces 959B uva156题目描述输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中大小写，按照字典序进行排序。 输入1234ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIednoel dire Disk mace Rob dries# 输出1234567DiskNotEderaildrIedeyeladdersoon 解析其实这道题挺简单的，把所有单词变成小写，然后排序，然后放到map里面，没有重复的就输出，但是自己写的过程中还是出了点问题。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <map>#include <cctype&g...

c++/java思维导图各两张 c++ java还有一个网址，里面列出来了比较详细的思维导图 Java知识汇总——思维导图 转载自： Java基础知识思维导图 c++知识思维导图 C++初学者必看的知识思维导图

map和multimap 开始 c++有map和multimap两种容器，区别在于multimap允许重复元素，map则不允许，在头文件中< map >中定义 Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字(key)，每个关键字只能在map中出现一次，第二个可能称为该关键字的值(value)）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的 </div> 它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。 自动建立Key － value的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。 什么是一...

内存内存，内存才是永恒的真理 总的来说： 新建的对象开在 堆里 属性 开在 堆里的对象里 局部变量 参数变量 开在 栈里 由C/C++编译的程序占用的内存分的几部分栈栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。 堆堆区（heap）— 由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。 全局区（静态区）全局区（静态区）（static）— 全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。 文字常量区常量字符串就是放在这里的，程序结束后由系统释放 。 程序代码区存放函数体的二进制代码。 变量，对象，内存 Java把内存划分成两种：一种是栈内存，一种是堆内存。在函数中定义的一些基本类型的变量和对象的引用变量都在函数的堆栈中分配 。 当在一段代码块定义一个变量时，Java就在栈中为这个变量分配内存空间，当超过变量的作用域后，J...

一次糟糕的面试前几天去面试学校的天高工作室，在半小时的一对多面试后，结果不如人意，归纳起来主要是自己的基础有点慌，加上自己总是在面试时开启的“暴走”状态，可算是凉凉。事后问面试过我的一个师兄，对方回答说：”我们觉得你的知识广度很广，但是深度还不够。“主要记录下面试时问到的几个不懂的基础部分吧（其实还是自己的基础不够扎实）,以便以后补上漏洞 堆和栈的区别这个问题其实是很经典的问题，堆和栈的区别倒是在大一上学期看过，可是隔了这么久忘了也是很正常。 动态链表那时候面试的一位老师问我有没有亲自写过动态链表的实现，emmm，上学期倒是学过基本的数据结构，也写过一些数据结构的实现，但是印象中没有学过动态链表这种东西。记得大一上学期倒是用链表解决过一道题，不过到现在，也是忘了，凉了。 变量，指针，内存一位师兄在面试的时候提到过了数组变量在内存中是怎么存在，而且指针在内存是怎么进行运作的，同时还问了下定义一个指针指向数组有什么用？记得那时候回答得可不是很好，内存这方面的知识倒是有点缺乏，最近学java，老师也说过了内存的一点知识，得找个时间巩固了下。 大数据在开发中的作用 emmm，这个倒是有点...

异或一些应用 参考:感受异或的神奇它的规则是若参加运算的两个二进位同号，则结果为0（假）；异号则为1（真）。即0∧0＝0，0∧1＝1，1∧1＝0 快速比较两个值可以用a^b == 0来快速比较两个值，效率会更高 使某些特定的位翻转0 ^ 1 = 1 1 ^ 1 = 0 例如：翻转10100001的第6位，答案：可以将该数与00100000进行按位异或运算：10100001 ^ 00100000 = 10000001 判断一个二进制数中1的数量是奇数还是偶数求10100001中1的数量是奇数还是偶数； 答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1 不使用其他空间，交换两个值123a = a ^ b;b = a ^ b; //a ^ b ^ b = a ^ 0 = a;a = a ^ b; 一个整型数组里除了N个数字之外，其他的数字都出现了两次，找出这N个数字从{A B C B C D A}找出单个字母的D 用到： A ^ A = 0; 异或满足交换律、结合律 12345A ^ B ^...

声明简介、比较函数、结构体排序 开始 排序用的函数是sort函数，包含在< algorithm >文件中。 sort()不仅可以用来给数字排序，还可以给字符串排序，默认的是升序，如果需要降序的话，可以自己写一个cmp回调函数（函数名可自拟，通常用cmp），然后在sort函数中，加上（cmp）函数名即可。 实现原理：sort并不是简单的快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和推排序。系统会根据你的数据形式和数据量自动选择合适的排序方法，这并不是说它每次排序只选择一种方法，它是在一次完整排序中不同的情况选用不同方法，比如给一个数据量较大的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，他会选择推排序。 具体函数实现，请参考：http://www.cnblogs.com/fengcc/p/5256337.html 声明简介函数声明 12345678#include <algorithm>template< class RandomIt（随机迭代器...