《编程之美》读书笔记12： 3.8 求二叉树中节点的最大距离 & 问题： 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。 & 实际上就是求树的直径。若采用“动态规划方法”思想，会将该问题分解成“具有最大距离两点间的路径是否经过根节点”两个子问题，然后再对这两个子问题求解判断。实际上，不必这么麻烦。距离最远的两点必然在以某个节点A为根的子树上，它们间的路径必然经过该子树的根节点A。因而，以任意一个节点B为根的子树，计算出经过该子树根节点B的最大距离，则所有最大距离的最大值就是所要求的二叉树的最大距离，即“树的直径”。而经过树的根节点的最大距离为：左子树的高度+右子树的高度+2（假设空节点的高度为-1），因而，原问题等同于“计算每个节点的左子树和右子树的高度和，取最大值”。
struct&Node&{&&Node&*&&Node&*&&int&};static&int&tree_height(Node*&root,&int&&max_distance){&&//每碰到一个子节点，高度自增1，可以设空节点高度为-1，&&//避免计算高度时对空节点的判断。&&if&(root&==&NULL)&return&-1;&&int&left_height&=&tree_height(root-&left,&max_distance)&+&1;&&int&right_height&=&tree_height(root-&right,&max_distance)&+&1;&&int&distance&=&left_height&+&right_&&if&(max_distance&&&distance)&max_distance&=&&&return&&left_height&&&right_height&?&left_height&:&right_}int&tree_diameter(Node*&root){&&int&max_distance&=&0;&&tree_height(root,&max_distance);&&return&max_}
阅读(...) 评论()4243人阅读
多重背包问题：
有N种物品和容量为V的背包，若第i种物品，容量为v[i]，价值为w[i]，共有n[i]件。怎样装才能使背包内的物品总价值最大？
网上关于&多重背包&的资料倒是不少，但是关于怎么实现O(N*V)算法的资料，真得好少呀，关于&单调队列&那部分算法，又没说明得很清楚，看了几遍没看懂原理，只好自己动脑去想怎么实现O(N*V)算法。
若用F[i][j]表示对容量为j的背包，处理完前i种物品后，背包内物品可达到的最大总价值，并记m[i] = min(n[i], j / v[i])。放入背包的第i种物品的数目可以是：0、1、2&&，可得：
F[i][j] = max { F[i - 1] [j & k * v[i] ] + k * w[i] }& (0 &= k &= m[i])&&&&&& ㈠
如何在O(1)时间内求出F[i][j]呢？
先看一个例子：取m[i] = 2, v[i] = v, w[i] = w, V & 9 * v，
并假设 f(j) = F[i - 1][j]，观察公式右边要求最大值的几项：
j = 6*v:&& f(6*v)、f(5*v)+w、f(4*v)+2*w 这三个中的最大值
j = 5*v:&& f(5*v)、f(4*v)+w、f(3*v)+2*w 这三个中的最大值
j = 4*v:&& f(4*v)、f(3*v)+w、f(2*v)+2*w 这三个中的最大值
显然，公式㈠右边求最大值的几项随j值改变而改变，但如果将j = 6*v时，每项减去6*w，j=5*v时，每项减去5*w，j=4*v时，每项减去4*w，就得到：
j = 6*v:&& f(6*v)-6*w、f(5*v)-5*w、f(4*v)-4*w 这三个中的最大值
j = 5*v:&& f(5*v)-5*w、f(4*v)-4*w、f(3*v)-3*w 这三个中的最大值
j = 4*v:&& f(4*v)-4*w、f(3*v)-3*w、f(2*v)-2*w 这三个中的最大值
很明显，要求最大值的那些项，有很多重复。
根据这个思路，可以对原来的公式进行如下调整：
假设d = v[i]，a = j / d，b = j % d，即 j = a * d + b，代入公式㈠，并用k替换a - k得：
F[i][j] = max { F[i - 1] [b + k * d] - k * w[i] } + a * w[i]&& (a & m[i] &= k &= a)&&& ㈡
对F[i - 1][y] （y= b& b+d& b+2d& b+3d& b+4d& b+5d& b+6d& && j）
F[i][j]就是求j的前面m[i] + 1个数对应的F[i - 1] [b + k * d] - k * w[i]的最大值，加上a * w[i]，如果将F[i][j]前面所有的F[i - 1][b + k * d] & k * w放入到一个队列，那么，F[i][j]就是求这个队列最大长度为m[i] + 1时，队列中元素的最大值，加上a * w[i]。因而原问题可以转化为：O(1)时间内求一个队列的最大值。
该问题可以这样解决：
① 用另一个队列B记录指定队列的最大值（或者记录最大值的地址），并通过下面两个操作保证队列B的第一个元素（或其所指向的元素）一定是指定队列的当前最大值。
② 当指定队列有元素M进入时，删除队列B中的比M小的（或队列B中所指向的元素小等于M的）所有元素，并将元素M（或其地址）存入队列B。
③ 当指定队列有元素M离开时，队列B中的第一个元素若与M相等（或队列B第一个元素的地址与M相等），则队列B的第一个元素也离队。
经过上述处理，可以保证队列B中的第一个元素（或其指向的元素）一定是所指定队列所有元素的最大值。显然队列B的元素（或其所指向的元素）是单调递减的，这应该就是《背包九讲》中的提到的&单调队列&吧，初看的时候被这个概念弄得稀里糊涂，网上的资料提到&维护队列的最大值&，刚开始还以为是维护这个单调队列的最大值，对其采用的算法，越看越糊涂。其实，只要明白用一个&辅助队列&，求另一个队列的最值，那么具体的算法，和该&辅助队列&的性质（单调变化），都很容易推导出来。
在多重背包问题中，所有要进入队列的元素个数的上限值是已知的，可以直接用一个大数组模拟队列。
&多重背包&通用模板:
//&多重背包&通用模板
const int MAX_V = 100004;
//v、n、w：当前所处理的这类物品的体积、个数、价值
//V：背包体积， MAX_V：背包的体积上限值
//f[i]：体积为i的背包装前几种物品，能达到的价值上限。
inline void pack(int f[], int V, int v, int n, int w)
if (n == 0 || v == 0)
if (n == 1) {
for (int i = V; i &= --i)
if (f[i] & f[i - v] + w) f[i] = f[i - v] +
if (n * v &= V - v + 1) {
//完全背包(n &= V / v)
for (int i = i &= V; ++i)
if (f[i] & f[i - v] + w) f[i] = f[i - v] +
int va[MAX_V], vb[MAX_V];
//va/vb: 主/辅助队列
for (int j = 0; j & ++j) {
//多重背包
int *pb = va, *pe = va - 1;
//pb/pe分别指向队列首/末元素
int *qb = vb, *qe = vb - 1;
//qb/qe分别指向辅助队列首/末元素
for (int k = j, i = 0; k &= V; k += v, ++i) {
== pb + n) {
//若队列大小达到指定值，第一个元素X出队。
if (*pb == *qb) ++
//若辅助队列第一个元素等于X，该元素也出队。
int tt = f[k] - i *
//元素X进队
//删除辅助队列所有小于X的元素，qb到qe单调递减，也可以用二分法
while (qe &= qb && *qe & tt) --
//元素X也存放入辅助队列
f[k] = *qb + i *
//辅助队列首元素恒为指定队列所有元素的最大值
多重背包特例：物品价值和体积相等（w = v）
由于w = v，上面的代码可进行如下修改：
入队的元素： tt = f[k] - (k / v) * w = f[k] - (k - j) = f[k] - k + j
&&& 返回的最大值：*qb + (k / v) * w =& *qb + k - j
由于j是定值，可调整入队的元素为: f[k] - k，最大值为 *qb + k
但这种做法相当低效。实际上，这相当于一个&覆盖&问题：在放入前i个物品后，体积为j的背包，只存在两种状态：是否能刚好装满，也就是，是否能被覆盖。因而只要记录下该状态就可以了，前面的分析进行相应的调整：
对F[i - 1][y] （y= b& b+d& b+2d& b+3d& b+4d& b+5d& b+6d& && j）
F[i][j]就是求j的前面m[i] + 1个数对应的F[i - 1] [b + k * d]（其值为0或1）的最大值，即j前面的m[i] + 1个0、1数据中是否存在1，这又可以简化为判断它们的和是否不等于0。
const int MAX_V = 100004;
//w = v 特例
inline void pack(bool f[], int V, int v, int n)
if (n == 0 || v == 0)
if (n == 1) {
for (int i = V; i - v &= 0; --i)
if (! f[i] && f[i - v]) f[i] =
//if (f[i - v]) f[i] =
if (n * v &= V - v + 1) {
//完全背包 n &= V / v
for (int i = i &= V; ++i)
if (! f[i] && f[i - v]) f[i] =
//if (f[i - v]) f[i] =
bool va[MAX_V];
for (int j = 0; j & ++j) {
//多重背包
bool *pb = va, *pe = va - 1;
size_t sum = 0;
for (int k = k &= V; k += v) {
if (pe == pb + n) sum -= *pb++;
//队列已满，队首元素出队
*++pe = f[k];
sum += f[k];
if (! f[k] && sum != 0) f[k] =
//f[k] = (bool)
另外，可以倒着读数据，这样就不需要额外使用一个数组存放临时数据：
//w = v 特例
inline void pack(bool f[], int V, int v, int n)
if (n == 0 || v == 0)
if (n == 1) {
for (int i = V; i - v &= 0; --i)
if (! f[i] && f[i - v]) f[i] =
//if (f[i - v]) f[i] =
if (n * v &= V - v + 1) {
//完全背包 n &= V / v
for (int i = i &= V; ++i)
if (! f[i] && f[i - v]) f[i] =
//if (f[i - v]) f[i] =
for (int j = 0; j & ++j) {
//多重背包
int k = V - j, sum = 0;
//前n + 1个元素入队，前面的判断可以保证： V - j - n * v & 0
for (; k &= std::max(0, V - j - n * v); k -= v) sum += f[k];
for (int i = V - i & 0; k -= v, i -= v) {
if (f[i]) --
//出队: sum -= f[i]
else if (sum != 0) f[i] =
//int tt = f[i]; f[i] = (bool) sum -=
if (k &= 0) sum += f[k];
前面的代码，都在循环中对队列的元素个数进行判断，这可以通过下面的方法避免，将循环拆分成两部分：一部分都有入队和出队操作、另一部分只有入队（或出队）操作。
对该特例，还有一种O(N * V)解法：用一个数组记录当前物品已经使用数，关键代码：
if (! f[i] && f[i - v] && count[i - v] & n)
f[i] = true, count[i] = count[i - v] + 1;
每计算一类物品，count数组都要初始化一次，比较费时，可以再用一个数组记录上一次处理的物品编号，通过判断上一次放入那一类的物品编号与当前这类物品编号是否一致（不一致时，相当于count[i]值为0的情况），从而避免对count数组的初始化操作。count
for (int i = 0; i &= V; ++i)
count[i] = 0;
for (int i = i &= V; ++i) {
//多重背包
if (! f[i] && f[i - v] && count[i - v] & n) {
count[i] = count[i - v] + 1;
cur为当前这类物品的编号
for (int i = i &= V; ++i) {
//多重背包
if (! f[i] && f[i - v]) {
if (last[i - v] != cur)
count[i] = 1, last[i] = cur, f[i] =
else if (count[i - v] & n) {
count[i] = count[i - v] + 1;
for (int i = i &= V; ++i) {
//多重背包
if (f[i]) count[i] = 0;
else if (f[i - v]) {
if (i & 2 * v)
count[i] = 1, f[i] =
else if (count[i - v] & n) {
count[i] = count[i - v] + 1;
POJ 1742：有若干不同面值的纸币，问能组合出1到m中的几种面值？
#include&algorithm&
#include&cstdio&
#define AB 0
//MAX_N 物品种类数最大值 MAX_n每种物品数目的最大值，MAX_V背包体积最大值
const int MAX_N = 101, MAX_V = 100004;
//w = v特例
inline void pack(bool f[], int V, int v, int n, int& total)
//if (n == 0 || v == 0)
if (n == 1) {
for (int i = V; i - v &= 0; --i)
if (! f[i] && f[i - v]) f[i] = true, ++
if (n * v &= V - v + 1) {
//完全背包 n &= V / v
for (int i = i &= V; ++i)
if (! f[i] && f[i - v]) f[i] = true, ++
for (int j = 0; j & ++j) {
//多重背包
int k = V - j, sum = 0;
//前n + 1个元素入队，前面的判断可以保证： V - j - n * v & 0
for (; k &= V - j - n * k -= v) sum += f[k];
for (int i = V - i & 0; k -= v, i -= v) {
if (f[i]) --
//出队: sum -= f[i]
else if (sum != 0) f[i] = true, ++
//int tt = f[i]; f[i] = (bool) sum -=
if (k &= 0) sum += f[k];
struct Node {
int n, v, V;
bool operator&(const Node& other) const { return V & other.V;}
int main()
#if AB == 1
freopen("src.txt","r",stdin);
freopen("z-b.txt","w",stdout);
Node node[MAX_N];
bool f[MAX_V];
while (scanf("%d %d",&N,&V) != EOF) {
if (N + V == 0)
Node *np = node + N;
for (Node *p = p & ++p) scanf("%d", &p-&v);
for (Node *p = p & ++p) {
scanf("%d", &p-&n);
p-&V = std::min(p-&n * p-&v, V);
std::sort(node, np);
int total = 0;
for (int i = 1; i &= V; ++i) f[i] =
int mv = 0;
for (Node *p = p & np && total & V; ++p) {
mv = std::min(mv + p-&V, V);
pack(f,mv,p-&v,p-&n, total);
printf("%d/n",total);
用自己随机生成的数据测试了下，上面提到的几种方法，所用时间都是7秒多点，有排序的比没排序的稍微快点。但在POJ上提交的结果，不同代码的耗时相差挺大，快的在1秒左右，慢的接近1.5秒。
还有一种特例：
给定面值为1、2、5的纸币若干个，问其所不能支付的最低价格（假设为自然数）。
这可以用多重背包（或母函数）来解决，但实际上是有O(1)解法的。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：71470次
积分：1235
积分：1235
排名：第17996名
原创：50篇
评论：34条
(2)(2)(2)(1)(2)(1)(4)(2)(3)(5)(26)Free Flying Hearts
Downloads: 500 - 1,000
版本: V1.3
大小: 512K
本版本最新变化
Added slider to adjust the amount of hearts separately for each type of hearts.
Flying hearts. Amazingly beautiful hearts will fly on your desktop in conjunction with beautiful wallpaper.
For loved ones on Valentine's Day
11 来自评论
YouTube Now Shows Full Screen Vertical Videos
通过 Emmanuel Lund
Forget The Minions! It's All About The New Emoji Movie
通过 Anna Grace
8 Android Apps To Make The World A Better Place
通过 Jayne Deacon
情人节动态壁纸
?情人节动态壁纸?终于在这里为所有的浪漫主义在那里！情人节马上就要来了，所以开始准备这个最浪漫的节日永远！有了这个全新的Android&&免...
Valentine's Day Live WP
Valentine's Day live wallpaper.
Enjoy watching live effects of ge...
Hearts For Valentine's Day
Flying hearts. Amazingly beautiful hearts will fly on your desktop in...
情人节动态壁纸
? 情人节动态壁纸 ?是最浪漫的壁纸为您的移动。你准备好了情人节？如果你想成为浪漫！如果你想惊喜你的甜蜜情人节！下载&情人节动态壁纸&，并与...
Love Live Wallpaper
&Red hearts filled with love are waiting for somebody to download them...
Valentines Day Live Wallpaper
Valentine's Day live wallpaper.
Enjoy watching live effects of ge...
情人节 动态壁纸
最浪漫的所有假期终于来了 - 下载情人节动态壁纸，并与你的知己分享爱情的魔力！装饰你的平板电脑这个粉红色的背景，享受最美妙的感觉在世界上！不...
Position {{$index); ?>
Position {{$index); ?>
Position {{$index); ?>
Position {{$index); ?>
Position {{$index); ?>
Position {{$index); ?>
Position {{$index); ?>
下载 Free Flying Hearts
免费 - V1.3 - 512K
通过电邮下载
我们将向您发送一封电邮，因此您必须登录.
点击该按钮，然后扫描QR码直接将该APP下载到您的设备上。Android
Position 1
Position 1
Position 1
所有分类Android 游戏《编程之美》读书笔记01： 1.2中国象棋将帅问题
&&& 刚看到题时，首先想到的是除法计算除数的商和余数（eax和edx）。后来才想到C/C++中需要动态多维数组时，new一维数组来模拟多维数组时所进行的多维数组的下标和实际偏移量的转换，我想很多人学习C或C++时都做过这种事吧。
&&& 本以为题目要求输出将帅在棋盘上的具体位置，如d10、f1，但书中的解法给的是相对位置，解决起来更简单。解法一用了一堆令人讨厌的宏，代码实在不美，解法三和解法一本质是一样的，虽然解法三只定义了一个结构体，但结构体内有两个变量，总共有三个变量，不合题意才对。
&&&& 要将一个变量i拆成两个，可以根据它的二进制表示分别取出连续几位，比如第0-3位和第4-7位，读变量时，取出变量i相应的几位，存变量时，再更新变量i的对应几位。另外，利用位置的对称性，可以一次输出两个，减少循环次数。
下面的代码和解法一类似，但是一次输出两个，减少了循环次数，并且没有用到除法，如果不考虑C++ IO效率的影响，会比解法二和解法三都高效。
//外层循环变量b使用i的第4-7位，初始值为1，最大值为8。
//内层循环变量a使用i的第0-3位，初始值为b+1，最大值为9。
for (unsigned i = 0x10; i & 0x90; i += 0x10)
for (i= (i & 0xF0) | (i && 4); (++i & 0xF) & 10; )
if (((i & 0xF) - (i && 4)) != 3 && ((i & 0xF) - (i && 4)) != 6)
std::cout && "A=" && (i && 4)
&& ", B="&& (i & 0xF) && "/n"
&& "A=" && (i & 0xF) && ", B="&& (i && 4)
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：71472次
积分：1235
积分：1235
排名：第17996名
原创：50篇
评论：34条
(2)(2)(2)(1)(2)(1)(4)(2)(3)(5)(26)安徽小伙求帮助，希望版主大大让通过
发表时间：
日 13:51:40
幻龙九封尽
请选择要设置的颜色：
请输入楼层数：
请输入楼层数：
该道具可显示帖子内所有匿名用户，但仅使用者本人能看到：
该道具可将帖子内的匿名发言用户恢复为正常显示昵称，并以红色醒目显示，为匿名终结者，且所有人都可以看到！
幻灵九峰尽
请输入回复置顶区的楼层数：
请输入楼层数：
麻烦看到的猫友们多帮忙转载下，土豪猫友请帮帮我同学，我们一个班的力量太小了，望猫友大大们有钱的出钱，没钱的出力转载下，不管你捐1元还是2元，对我的同学来说，都是一份希望，图上有我同学母亲的号码，不放心的可以求证下，最可恨的是当地政府居然不愿意开证明，拿人民的钱居然不管人民的死活，现在我们全班都在帮助他去寻求帮助，希望好心人们都能伸出援手，谢谢。我们是安徽省六安市皖西学院机械设计制造及其自动化的学生，现在学校也在帮我们，好心人们还可以打电话去学校求证下，谢谢。
麻烦看到的猫友们多帮忙转载下，土豪猫友请帮帮我同学，我们一个班的力量太小了，望猫友大大们有钱的出钱，没钱的出力转载下，不管你捐1元还是2元，对我的同学来说，都是一份希望，图上有我同学母亲的号码，不放心的可以求证下，最可恨的是当地政府居然不愿意开证明，拿人民的钱居然不管人民的死活，现在我们全班都在帮助他去寻求帮助，希望好心人们都能伸出援手，谢谢。我们是安徽省六安市皖西学院机械设计制造及其自动化的学生，现在学校也在帮我们，好心人们还可以打电话去学校求证下，谢谢。
热门回复区，由被顶最多的回复及置顶回复组成！
共0条热门回复，展开
收起热门回复
0条跟帖，4344人参与
贴贴精彩热图
财务密码：
猜你也喜欢}