01背包问题 问题描述 给定 N 种物品和一个最大载重量为 C 的背包,物品 i 的重量是 wi,其价值为 vi 。 问:应该如何选择装入背包的物品,使得装入背包中的物品的总价值最大? 问题分析 对于每个物品,只能选择装或者不装,不能选择只装物体的一部分,因此不能使用单位重量的价值进行排序的方法(贪心)来解决,需要用到动态规划来解决。 动态规划的三个核心 最优子结构 边界 状态转移方程 对于该问题而言,由于第i+1件物品只有两种选择(选与不选),因此前i+1件产品的最优解就是前,子结构就是前i件物品装在承重为j的容器中,可以用result[i][j]来表示。 边界就是在只装第一件物品时的情况。 通过上面的对子结构的分析,可以得到状态转移方程: 1. j < w[i]时,即剩余载重量不足以装下当前物品,应有最优解即是前i-1件时的解,result[i][j] = result[i-1][j] 2. j >= w[i]时,即还可以装下当前物 继续阅读 >>


王良 18/06/03 19:49:16
题目链接 链表中环的入口结点(牛客网) 题目分析 类似于追及问题: 如何判断有环的存在? 在追及问题中,我们可以用两个速度不同的物体从同一地点出发,如果相遇则证明存在环(可用反证法证明,若不存在环,则速度不同的物体从同一地点出发则一定不会相遇),因此可以类比过来,定义两个指针fast、slow,令两指针以不同速度向后指,则相遇时证明有环存在,若fast指向NULL,则不存在环。 怎么找到环的入口结点? 首先说方法:在问题一中两指针相遇后,让一个指针从头结点开始,另一个从相遇结点开始,并以相同速度向后指,再次相遇时就是环的入口结点。 证明: 1)假设存在环,fast以速度2运行,slow以速度1运行,在slow走到入口t时,如图(m1为在slow首次到t时fast的位置,a为h到t的距离,b为t到m1的距离,n为环的周长): 由图知fast走的距离为a+b+xn,slow走的距离为a,又v(fast) = 2*v(slow),所以x(fast) = 2*x(slow),即2a = 继续阅读 >>


王良 18/05/24 23:03:05
继承与动态内存分配 在基类或派生类中含有指针时,要考虑内存分配情况(new与delete),还要考虑在进行对象间赋值时指针隐藏的问题(使用默认复制构造函数在析构时会造成原对象中的指针指向的内存空间被释放,为浅复制) 因此需要: 1. 重载运算符’=‘、’<<‘,实现深度复制; 2. 在构造函数中使用new进行动态内存分配,在析构函数中使用delete进行内存释放; 3. 将析构函数声明为虚函数 在以下代码中还有一个小技巧来简化代码,即代码重用,在后续代码中使用已定义过的代码,例如:在C的构造函数中使用已经定义过的A的构造函数,这样就可以只对C类新增的数据部分进行初始化。 #include <iostream> #include <string> #include <cstring> using namespace std; class A { private: char *label; //使用指针,需要动态分配内存 继续阅读 >>


王良 18/05/16 23:37:26
友元 一般来说,类内的私有数据是对外不可见的,但在有些情况下,我们需要在类外对该类的私有数据进行访问,这就需要用到一种新技术——友元(friend),即在声明前添加关键字friend。 友元关系是单向的,即如果A是B的友元,但B不一定是A的友元; 友元关系无传递性,即如果A是B的友元,B是C的友元,但A不一定是C的友元。 1. 友元函数 友元函数是指某些非类成员函数,但可以访问类内的私有数据。 #include <iostream> using namespace std; class A { private: int data; public: A() : data(1) {} friend void show( const A& t ); //添加friend定义友元函数 }; /* 友元函数在类外声明时不加friend */ void show( const A& t ) { cout << 继续阅读 >>


王良 18/05/07 22:34:40
在c++的STL中有函数可以直接对数组元素进行全排列,即next_permutation和pre_permutation,这两个函数都可以实现全排列,只是排列的顺序不同,next_permutation作用为向后排序,而pre_permutation作用为向前排序。 需要头文件#include <algorithm> 示例 #include <iostream> #include <algorithm> using namespace std; int main() { int nums[10]; for( int i = 0; i < 10; i++ ) { nums[i] = i + 1; } int n; cin >> n; do { for( int i = 0; i < n; i++ ) { cout << 继续阅读 >>


王良 18/04/24 22:50:15
jsoncpp 一. json基础 类型: 1. Json::Value为主要数据类型; 2. Json::Reader将文件流或字符串创解析到Json::Value中,主要使用parse函数;3. Json::Writer:与JsonReader相反,将Json::Value转换成字符串流等,Writer类是一个纯虚类,并不能直接使用。在此我们使用 Json::Writer 的子类:son::FastWriter(将数据写入一行,没有格式),Json::StyledWriter(按json格式化输出,易于阅读) 二. 解析json 1. 从内存解析json void f() { Json::Value root; Json::Reader reader; char str[] = "{\"name\" : \"liushall\", \"age\" : 20, \ \"files\" : [\"1.json\", \"2.json\ 继续阅读 >>


王良 18/04/15 23:47:04
一. 静态多态 1. 何为静态多态? 又称编译期多态,即在系统编译期间就可以确定程序将要执行哪个函数。例如:函数重载,通过类成员运算符指定的运算。 2. 示例代码 函数重载示例: class A { public: A() {} A( int x ) {} void f() {} void f( int x ) {} }; class B { public: B() {} void f() {} void f( int x ) {} }; 以上,类A中两个A()是函数重载,两个f()是函数重载,类B同理。 二. 动态多态 1. 何为动态多态? 动态多态是利用虚函数实现运行时的多态,即在系统编译的时候并不知道程序将要调用哪一个函数,只有在运行到这里的时候才能确定接下来会跳转到哪一个函数。 动态多态是在虚函数的基础上实现的,而实现的条件有: (1) 在类中声明为虚函数 (2) 函数的函数名,返回值,函数参数个数,参数类 继续阅读 >>


王良 18/04/15 19:00:38
需要虚析构函数的原因: 首先看一下这段代码: #include <iostream> using namespace std; class A { private: int *a; public: A() { a = new int; cout << "A::A() is called.\n"; } ~A() { delete a; cout << "A::~A() is called.\n"; } void print() { cout << "A::print() is called.\n"; } }; class B : public A { private: int *b; public: B() { b = new int; cout << "B::B() is called.\n"; } ~B() { delete b; cout << "B::~ 继续阅读 >>


王良 18/04/15 11:40:39
解决toggled无法触发setVisible 解决方法: 在QT Designer中,创建QPushButton时需要将按钮修改为checkable。在默认情况下,checkable是不选中的,默认为触发按钮(trigger button),也就是按下之后立即弹起来,而选为checkable后,就成为了切换按钮(两种状态:按下/弹起)。这样就可以切换按钮状态来实现窗口显示与否。 参考: http://blog.csdn.net/humanking7/article/details/44095283 作者:liushall 发表于 2018/03/17 12:28:38 原文链接 https://blog.csdn.net/liushall/article/details/79590905 继续阅读 >>


王良 18/03/17 12:28:38
均分纸牌 题目描述 Description 有 N 堆纸牌,编号分别为 1,2,…, N。每堆上有若干张,但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌,然后移动。   移牌规则为:在编号为 1 堆上取的纸牌,只能移到编号为 2 的堆上;在编号为 N 的堆上取的纸牌,只能移到编号为 N-1 的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。   现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。   例如 N=4,4 堆纸牌数分别为:   ① 9 ② 8 ③ 17 ④ 6   移动3次可达到目的:   从 ③ 取 4 张牌放到 ④ (9 8 13 10) -> 从 ③ 取 3 张牌放到 ②(9 11 10 10)-> 从 ② 取 1 张牌放到①(10 10 10 10)。 输入描述 Input Description 第一行N(N 堆纸牌,1 <= N <= 100) 第二行A1 A2 … An (N 堆纸牌,每堆纸 继续阅读 >>


王良 18/03/05 16:55:40