google-perftools 剖析程序性能

1,首先下载并安装google-perftools:注意了,如果是64位系统:那么你需要做:

1)先安装libunwind或者2)在configure时添加--enable-frame-pointers.

那么首先说说如何安装libunwind:

wget http://download.savannah.gnu.org/releases/libunwind/libunwind-1.0.1.tar.gz
tar zxvf libunwind-0.99.tar.gz
cd libunwind-0.99/
CFLAGS=-fPIC ./configure --prefix=/usr
make CFLAGS=-fPIC
make CFLAGS=-fPIC install

到这里安装libunwind完成.

如果是使用添加--enable-frame-pointers的方式,先不管,咱们往下走.

下载并安装google-perftools:

wget http://google-perftools.googlecode.com/files/google-perftools-1.7.tar.gz
tar xzvf google-perftools-1.7.tar.gz
cd google-perftools-1.7

然后开始配置:
./configure --prefix=/usr --enable-frame-pointers
在这里注意这步,如果是32位系统,可以不添加 --enable-frame-pointers,如果是64位系统,并且你之前没有安装libunwind,那么你一定要添加这个:--enable-frame-pointers

编译并安装:

make
make install

到这里安装google-perftools完成了但未生效,接下来需要使google-perftools生效:

echo "/usr/local/lib" > /etc/ld.so.conf.d/usr_local_lib.conf
/sbin/ldconfig

注意，这里的双引号是英文的。

到这里安装google-perftools完成.

dot: command not found”.
The reason is that I did not install graphviz Graph Visualization Tools, after installed it, the error went away.

http://www.ibm.com/developerworks/cn/linux/l-cn-googleperf/index.html?ca=drs-

__PRETTY_FUNCTION__ 可显示当前类的函数名完整信息，包括参数类型，比__FUNCTION__更多信息。

模板类的：

template <class T>

class animal

{

private:

T  n;

public:

animal():n(1){};

animal(T  c);

~animal(){};

bool eat();

}

template <class T>

bool animal<T>::eat()

{

if(n)

{

cout << "eat enough"<<endl;

return ture;

}

else

return false;

}

二、可变参数
我们在C语言编程中有时会遇到一些参数个数可变的函数,例如printf()函数,其函数原型为:
int printf( const char* format,  ...);

它除了有一个参数format固定以外,后面跟的参数的个数和类型是可变的（用三个点"…"做参数占位符）,实际调用时可以有以下的形式:
printf("%d",i);
printf("%s",s);
printf("the number is %d ,string is:%s", i, s);

范例：

int __fnAdd(int start, ...)

{

va_list arg_ptr;

int sum=0;

int nArgValue =start;

int nArgCout=0;

va_start(arg_ptr,start);

do

{

sum+=nArgValue;

++nArgCout;

printf("the %d th arg: %d\n",nArgCout,nArgValue);

printf("\n");

nArgValue = va_arg(arg_ptr,int);

} while(nArgValue != 0);

printf("the sum= %d\n",sum);

va_end(arg_ptr);

printf("\n");

return sum;

}

int main()
{
printf("%d\n", __fnAdd(1,2,3,0);       //以数字0为结束
printf("%d\n", __fnAdd(1,2,3,5,0);
getch();
return 0;
}

解释一下这些代码

从这个函数的实现可以看到,我们使用可变参数应该有以下步骤:

⑴由于在程序中将用到以下这些宏:
void va_start( va_list arg_ptr, prev_param );
type va_arg( va_list arg_ptr, type );
void va_end( va_list arg_ptr );
va在这里是variable-argument(可变参数)的意思.
这些宏定义在stdarg.h中,所以用到可变参数的程序应该包含这个头文件.

⑵函数里首先定义一个va_list型的变量,这里是arg_ptr,这个变量是存储参数地址的指针.因为得到参数的地址之后，再结合参数的类型，才能得到参数的值。

⑶然后用va_start宏初始化⑵中定义的变量arg_ptr,这个宏的第二个参数是可变参数列表的前一个参数,即最后一个固定参数.

⑷然后依次用va_arg宏使arg_ptr返回可变参数的地址,得到这个地址之后，结合参数的类型，就可以得到参数的值。

⑸设定结束条件，这里的条件就是判断参数值是否为-1。注意被调的函数在调用时是不知道可变参数的正确数目的，程序员必须自己在代码中指明结束条件。至于为什么它不会知道参数的数目，读者在看完这几个宏的内部实现机制后，自然就会明白。

(二)可变参数在编译器中的处理
我们知道va_start,va_arg,va_end是在stdarg.h中被定义成宏的, 由于1)硬件平台的不同 2)编译器的不同,所以定义的宏也有所不同,下面看一下VC++6.0中stdarg.h里的代码（文件的路径为VC安装目录下的\vc98\include\stdarg.h）
typedef char *   va_list;
#define _INTSIZEOF(n) ((sizeof(n) + sizeof(int) - 1) & ~(sizeof(int) - 1) )
#define va_start(ap,v)   ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,t)     ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
#define va_end(ap)       ( ap = (va_list)0 )

下面我们解释这些代码的含义：

1、首先把va_list被定义成char*，这是因为在我们目前所用的PC机上，字符指针类型可以用来存储内存单元地址。而在有的机器上va_list是被定义成void*的

2、定义_INTSIZEOF(n)主要是为了某些需要内存的对齐的系统.这个宏的目的是为了得到最后一个固定参数的实际内存大小。在我的机器上直接用sizeof运算符来代替，对程序的运行结构也没有影响。（后文将看到我自己的实现）。

3、va_start的定义为 &v+_INTSIZEOF(v) ,这里&v是最后一个固定参数的起始地址，再加上其实际占用大小后，就得到了第一个可变参数的起始内存地址。所以我们运行va_start(ap, v)以后,ap指向第一个可变参数在的内存地址,有了这个地址，以后的事情就简单了。

这里要知道两个事情：
⑴在intel+windows的机器上，函数栈的方向是向下的，栈顶指针的内存地址低于栈底指针，所以先进栈的数据是存放在内存的高地址处。
(2)在VC等绝大多数C编译器中，默认情况下，参数进栈的顺序是由右向左的，因此，参数进栈以后的内存模型如下图所示：最后一个固定参数的地址位于第一个可变参数之下，并且是连续存储的。
|--------------------------|
|   最后一个可变参   |    ->高内存地址处
|--------------------------|
|--------------------------|
|   第N个可变参数                       |      ->va_arg(arg_ptr,int)后arg_ptr所指的地方,
|                                |      即第N个可变参数的地址。
|--------------- |
|--------------------------|
|   第一个可变参数                      |      ->va_start(arg_ptr,start)后arg_ptr所指的地方
|                                |      即第一个可变参数的地址
|--------------- |
|------------------------ --|
|                                |
|   最后一个固定参数                  |     -> start的起始地址
|-------------------------- |
|                                 |
|--------------------------|   -> 低内存地址处

(4) va_arg():有了va_start的良好基础，我们取得了第一个可变参数的地址，在va_arg()里的任务就是根据指定的参数类型取得本参数的值，并且把指针调到下一个参数的起始地址。
因此，现在再来看va_arg()的实现就应该心中有数了：
#define va_arg(ap,t)     ( *(t *)((ap += _INTSIZEOF(t)) - _INTSIZEOF(t)) )
这个宏做了两个事情，
①用用户输入的类型名对参数地址进行强制类型转换，得到用户所需要的值
②计算出本参数的实际大小，将指针调到本参数的结尾，也就是下一个参数的首地址，以便后续处理。

(5)va_end宏的解释：x86平台定义为ap=(char*)0;使ap不再 指向堆栈,而是跟NULL一样.有些直接定义为((void*)0),这样编译器不会为va_end产生代码,例如gcc在linux的x86平台就是这样定义的. 在这里大家要注意一个问题:由于参数的地址用于va_start宏,所以参数不能声明为寄存器变量或作为函数或数组类型. 关于va_start, va_arg, va_end的描述就是这些了,我们要注意的 是不同的操作系统和硬件平台的定义有些不同,但原理却是相似的.

(三)可变参数在编程中要注意的问题
因为va_start, va_arg, va_end等定义成宏,所以它显得很愚蠢, 可变参数的类型和个数完全在该函数中由程序代码控制,它并不能智能 地识别不同参数的个数和类型. 有人会问:那么printf中不是实现了智能识别参数吗?那是因为函数 printf是从固定参数format字符串来分析出参数的类型,再调用va_arg 的来获取可变参数的.也就是说,你想实现智能识别可变参数的话是要通过在自己的程序里作判断来实现的. 例如，在C的经典教材《the c programming language》的7.3节中就给出了一个printf的可能实现方式，由于篇幅原因这里不再叙述。

（四）小结:
1、标准C库的中的三个宏的作用只是用来确定可变参数列表中每个参数的内存地址，编译器是不知道参数的实际数目的。
2、在实际应用的代码中，程序员必须自己考虑确定参数数目的办法，如
⑴在固定参数中设标志-- printf函数就是用这个办法。后面也有例子。
⑵在预先设定一个特殊的结束标记，就是说多输入一个可变参数，调用时要将最后一个可变参数的值设置成这个特殊的值，在函数体中根据这个值判断是否达到参数的结尾。本文前面的代码就是采用这个办法.
无论采用哪种办法，程序员都应该在文档中告诉调用者自己的约定。
3、实现可变参数的要点就是想办法取得每个参数的地址，取得地址的办法由以下几个因素决定：
①函数栈的生长方向
②参数的入栈顺序
③CPU的对齐方式
④内存地址的表达方式
结合源代码，我们可以看出va_list的实现是由④决定的，_INTSIZEOF(n)的引入则是由③决定的，他和①②又一起决定了va_start的实现，最后va_end的存在则是良好编程风格的体现，将不再使用的指针设为NULL,这样可以防止以后的误操作。
4、取得地址后，再结合参数的类型，就可以正确的处理参数了。

Tags: 变参, 模板

softirq和tasklet都属于软中断，tasklet是softirq的特殊实现；workqueue是普通的工作队列。而工作队列是和软中断无关，仅仅是内核中的

一个内核线程在等待工作任务，工作队列可以发送工作任务。不过他们还是有个共同点，就是都有延后执行的作用

softirq是一种基本的底半部机制，有较强的加锁需求,仅仅用在一些对性能敏感的子系统中才会使用softirq。

tasklet建立在softirq之上，使用起来相对简单。严格要求的情况除外，一般都建议使用tasklet。

两者的不同主要是前者是可重用的，而后者不能。换句话说，softirq的不同实例可运行在不同的处理器上，而tasklet不可。

Linux系统中定义了如下几个softirq类型：
enum
{

HI_SOFTIRQ=0,
TIMER_SOFTIRQ,
NET_TX_SOFTIRQ,
NET_RX_SOFTIRQ,
BLOCK_SOFTIRQ,
BLOCK_IOPOLL_SOFTIRQ,
TASKLET_SOFTIRQ,
SCHED_SOFTIRQ,
HRTIMER_SOFTIRQ,
RCU_SOFTIRQ,        /* Preferable RCU should always be the last softirq */

NR_SOFTIRQS

};

总共10个softirq，tasklet是其中的一种。

延后的实现其实是通过一个变量(pending)的某些位置1来跟踪哪些softirq需要处理，比如该变量如果是00001010，因为bit 1, 3位置1，所以说明TIMER_SOFTIRQ和NET_RX_SOFTIRQ所对应的softirq需要处理

http://www.embexperts.com/viewthread.php?tid=92

1、softirq

软中断支持SMP，同一个softirq可以在不同的CPU上同时运行，softirq必须是可重入的。软中断是在编译期间静态分配的，它不像tasklet那样能被动态的注册或去除。kernel/softirq.c中定义了一个包含32个softirq_action结构体的数组。每个被注册的软中断都占据该数组的一项。因此最多可能有32个软中断。2.6版本的内核中定义了六个软中断：HI_SOFTIRQ、TIMER_SOFTIRQ、NET_TX_SOFTIRQ、NET_RX_SOFTIRQ、SCSI_SOFTIRQ、TASKLET_SOFTIRQ。
一般情况下，在硬件中断处理程序后都会试图调用do_softirq（）函数，每个CPU都是通过执行这个函数来执行软中断服务的。由于软中断不能进入硬中断部分，且同一个CPU上软中断的执行是串行的，即不允许嵌套，因此，do_softirq()函数一开始就检查当前CPU是否已经正出在中断服务中，如果是则 do_softirq()函数立即返回。这是由do_softirq（）函数中的 if (in_interrupt()) return; 保证的。

2、tasklet

引入tasklet，最主要的是考虑支持SMP，提高SMP多个cpu的利用率；不同的tasklet可以在不同的cpu上运行。tasklet可以理解为softirq的派生，所以它的调度时机和软中断一样。对于内核中需要延迟执行的多数任务都可以用tasklet来完成，由于同类tasklet本身已经进行了同步保护，所以使用tasklet比软中断要简单的多，而且效率也不错。tasklet把任务延迟到安全时间执行的一种方式，在中断期间运行，即使被调度多次，tasklet也只运行一次，不过tasklet可以在SMP系统上和其他不同的tasklet并行运行。在SMP系统上，tasklet还被确保在第一个调度它的CPU上运行，因为这样可以提供更好的高速缓存行为，从而提高性能。
与一般的软中断不同，某一段tasklet代码在某个时刻只能在一个CPU上运行，但不同的tasklet代码在同一时刻可以在多个CPU上并发地执行。Kernel/softirq.c中用tasklet_trylock()宏试图对当前要执行的tasklet（由指针t所指向）进行加锁，如果加锁成功（当前没有任何其他CPU正在执行这个tasklet），则用原子读函数atomic_read()进一步判断count成员的值。如果count为0，说明这个tasklet是允许执行的。如果tasklet_trylock()宏加锁不成功，或者因为当前tasklet的count值非0而不允许执行时，我们必须将这个tasklet重新放回到当前CPU的tasklet队列中，以留待这个CPU下次服务软中断向量TASKLET_SOFTIRQ时再执行。为此进行这样几步操作：（1）先关 CPU中断，以保证下面操作的原子性。（2）把这个tasklet重新放回到当前CPU的tasklet队列的首部；（3）调用__cpu_raise_softirq()函数在当前CPU上再触发一次软中断请求TASKLET_SOFTIRQ；（4）开中断。
软中断和tasklet都是运行在中断上下文中，它们与任一进程无关，没有支持的进程完成重新调度。所以软中断和tasklet不能睡眠、不能阻塞，它们的代码中不能含有导致睡眠的动作，如减少信号量、从用户空间拷贝数据或手工分配内存等。也正是由于它们运行在中断上下文中，所以它们在同一个CPU上的执行是串行的，这样就不利于实时多媒体任务的优先处理。

那么，什么情况下使用工作队列，什么情况下使用tasklet。如果推后执行的任务需要睡眠，那么就选择工作队列。如果推后执行的任务不需要睡眠，那么就选择tasklet。另外，如果需要用一个可以重新调度的实体来执行你的下半部处理，也应该使用工作队列。它是唯一能在进程上下文运行的下半部实现的机制，也只有它才可以睡眠。这意味着在需要获得大量的内存时、在需要获取信号量时，在需要执行阻塞式的I/O操作时，它都会非常有用。如果不需要用一个内核线程来推后执行工作，那么就考虑使用tasklet。

参考 ：http://blog.chinaunix.net/space.php?uid=14142730&do=blog&id=307753

Tags: 中断, 睡眠, 软, 队列

背包问题

是一个关于最优解的经典问题。通常被讨论的最多的，最经典的背包问题是0-1背包问题(0-1 Knapsack Problem)。它是一切背包问题及相关背包问题的基础。本篇博文将详细分析0-1背包问题，并给出0-1背包问题的几种解法，同时也对0-1背包问题的内涵进行延伸，丰富其外延至完全背包问题和多重背包问题，并给出背包问题的算法实现过程：

一、0-1背包问题

有N件物品和一个容量为V的背包。第i件物品（每个物品只有一件）的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示选取物品i) 取得最大值。
在该问题中需要决定x1 .. xn的值。假设按i = 1，2，...，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品(即物品2，3，.，n)，背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。
在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1，[x2 ，.，xn ] 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一个更好的方案。
假设n=3, w=[100,14,10], p=[20,18,15], c= 116。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的条件，所得值为1 5，但因为[x2，x3 ]= [1，0] 同样符合容量条件且所得值为1 8，因此[x2，x3 ] = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为116。总之，如果子问题的结果[x2，x3 ]不是剩余情况下的一个最优解，则[x1，x2，x3 ]也不会是总体的最优解。在此问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示剩余容量为y，剩余物品为i，i + 1，...，n 时的最优解的值，即：利用最优序列由最优子序列构成的结论，可得到f 的递归式为：
当j>=wi时： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
当0<=j<wi时：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始时背包问题的最优解。
以本题为例：若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最优解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
现在计算xi 值，步骤如下：若f ( 1 ,c) =f ( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用f (2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1.n) 值。
在该例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2 及x3，此时r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此时r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。

（1）递归求解

算法如下：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6

using namespace std;
int nVol[GOODSNUM];
int nValue[GOODSNUM];

int knapsack(int itemIndex,int vol);

void main()
{
int i=0,j=0;
while(i<GOODSNUM)
{
cout<<"input the "<<i+1<<"th item(volume and value):";
cin>>nVol[i]>>nValue[i];
i++;
}
cout<<"The max value is: "<<knapsack(GOODSNUM,CAPACITY)<<endl;
}

int knapsack(int itemIndex,int vol)
{
if (itemIndex==0||vol==0)
{
return 0;
}
else if (vol>=nVol[itemIndex] && knapsack(itemIndex-1,vol)<knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex])
{
return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];
}
else
return knapsack(itemIndex-1,vol);
}

分析：递归求解，求解过程中的绝大部分变量存在重复求解的过程，算法的效率较低，有待改进；那怎么改进呢？最有效的是用数组保存每次计算的结果，不用重复计算，于是有二维数组求解。

（2）二维数组求解

算法如下：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6

using namespace std;

void main()
{
int i=1,j;
int v[GOODSNUM] = {10,12,40,40,40,15};
int c[GOODSNUM] = {1,2,3,5,2,1};
int fun[GOODSNUM+1][CAPACITY+1];
for (i=1;i<=GOODSNUM;i++)
{
fun[i][0] = 0;
}
for (i=1;i<=CAPACITY;i++)
{
fun[0][i] = 0;
}
for (i=1;i<=GOODSNUM;i++)
{
for (j=1;j<=CAPACITY;j++)
{
if (j<c[i-1])
{
fun[i][j] = fun[i-1][j];
}
else if (fun[i-1][j]<fun[i-1][j-c[i-1]] + v[i-1])
{
fun[i][j] = fun[i-1][j-c[i-1]] + v[i-1];
}
else
fun[i][j] = fun[i-1][j];
}
}
cout<<"The max value is: "<<fun[GOODSNUM][CAPACITY]<<endl;
}

分析：二维数组求解方法相比递归求解要优越很多，但是其空间复杂度依然较高，还有继续改进的余地吗？一维数组是否可行呢？答案是肯定的

（3）一维数组求解

算法分析：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6

using namespace std;

void main()
{
int nVolume[GOODSNUM] = {1,2,3,5,2,1};
int nValue[GOODSNUM] = {10,12,40,40,40,15};
int selectTable[GOODSNUM][CAPACITY+1] = {0};
int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
int itemIndex,capIndex;
for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
{
for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0  注意此处与二维数组求解的区别
{
if (nKnapsack[capIndex]<nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex])
{
nKnapsack[capIndex] = nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex];
selectTable[itemIndex][capIndex] = 1;
}
else
nKnapsack[capIndex] = nKnapsack[capIndex];
}
}
cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
cout<<"The selected items are: ";
for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
{
if (selectTable[itemIndex][capIndex])
{
cout<<itemIndex+1<<" ";
capIndex = capIndex - nVolume[itemIndex];
}
}
cout<<endl;
}
分析：在一维数组实现中将空间复杂度由O(GOODSNUM*CAPACITY)降低到O(CAPACITY)并同时进行了代码优化，同时也给出了选择物品的编号。

二、完全背包问题

若你能给深入理解0-1背包问题和其深刻内涵，并真正明白一维数组求解背包问题后，下面的问题对你来说就相当容易了。

完全背包问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

求解分析：目标是转化为0-1背包问题。如将费用/容量为nVolume[itemIndex]的物品转化为CAPACITY/nVolume[itemIndex]相同费用和价值的物品，直接用前面的三种0-1背包问题求解。除此之外还有其它可行的求解方法吗？可以对0-1背包问题的状态方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}稍加分析可得完全背包问题的状态方程f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}，因而有以下算法实现过程，并最终给出了所选择的物品和选择该物品的数目。

实现算法：

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6

using namespace std;

void main()
{
int num,k,max;
int nVolume[GOODSNUM] = {1,4,3,5,5,3};
int nValue[GOODSNUM] = {2,8,40,60,10,3};
int selectTable[GOODSNUM][CAPACITY+1] = {0};
int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
int itemIndex,capIndex;
for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
{
for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0
{
num = 0;
max = nKnapsack[capIndex];
for (k=1;k<=CAPACITY/nVolume[itemIndex];k++)
{
if (capIndex>=k*nVolume[itemIndex] && max<nKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex])
{
max = nKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex];
num = k;
}
}
nKnapsack[capIndex] = max;
selectTable[itemIndex][capIndex] = num;
}
}
cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
cout<<"The selected items are: "<<endl;
for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
{
if (selectTable[itemIndex][capIndex])
{
cout<<itemIndex+1<<":"<<selectTable[itemIndex][capIndex]<<" ";
capIndex = capIndex - selectTable[itemIndex][capIndex]*nVolume[itemIndex];
}
}
cout<<endl;
}

三、多重背包问题

多重背包问题：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

多重背包问题基本求解方式同完全背包问题，唯一的是控制参数k的限制有所不同。只需要将完全背包问题实现中的k<=CAPACITY/nVolume[itemIndex]限制条件改为k<=CAPACITY/nVolume[itemIndex] && k<= n[i]即可。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

动态规划

Tags: 动态规划, 背包原理, 递归

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1]     A[2]     A[3]     A[4]     A[5]      A[6]     A[7]：

49        38       65       97       76       13        27

进行第一次交换后：   27        38       65       97       76       13        49

( 按照算法的第三步从后面开始找

进行第二次交换后：   27        38       49       97       76       13        65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后：   27        38       13       97       76       49        65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后：   27        38       13       49       76       97        65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27        38       13       49       76       97        65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态                                                {49     38     65     97     76     13     27}

进行一次快速排序之后划分为         {27     38     13}     49   {76     97     65}

分别对前后两部分进行快速排序     {13}    27    {38}

结束         结束      {49    65}    76    {97}

49   {65}         结束

结束

图6    快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，其目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1      2       3       4       5       6       7       8       9       10

45     36     18     53     72     30     48     93     15      36

I                                                                   J

（1）      36     36     18     53     72     30     48     93     15      45

（2）      36     36     18     45     72     30     48     93     15      53

（3）      36     36     18     15     72     30     48     93     45      53

（4）      36     36     18     15     45     30     48     93     72      53

（5）      36     36     18     15     30     45     48     93     72      53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。

一般来说，冒泡法是程序员最先接触的排序方法，它的优点是原理简单，编程实现容易，但它的缺点就是--程序的大忌--速度太慢。下面我介绍一个理解上简单但编程实现上不是太容易的排序方法，我不知道它是不是现有排序方法中最快的，但它是我见过的最快的。排序同样的数组，它所需的时间只有冒泡法的 4% 左右。我暂时称它为“快速排序法”。

“快速排序法”使用的是递归原理，下面我结合一个例子来说明“快速排序法”的原理。首先给出一个数组{53，12，98，63，18，72，80，46， 32，21}，先找到第一个数--53，把它作为中间值，也就是说，要把53放在一个位置，使得它左边的值比它小，右边的值比它大。{21，12，32， 46，18，53，80，72，63，98}，这样一个数组的排序就变成了两个小数组的排序--53左边的数组和53右边的数组，而这两个数组继续用同样的方式继续下去，一直到顺序完全正确。

我这样讲你们是不是很胡涂，不要紧，我下面给出实现的两个函数：

/*
n就是需要排序的数组，left和right是你需要排序的左界和右界，
如果要排序上面那个数组，那么left和right分别是0和9
*/

void quicksort(int n[], int left,int right)
{
int dp;
if (left<right)

{

/*
这就是下面要讲到的函数，按照上面所说的，就是把所有小于53的数放
到它的左边，大的放在右边，然后返回53在整理过的数组中的位置。
*/
dp=partition(n,left,right);

quicksort(n,left,dp-1);

quicksort(n,dp+1,right); //这两个就是递归调用，分别整理53左边的数组和右边的数组
}
}

我们上面提到先定位第一个数，然后整理这个数组，把比这个数小的放到它的左边，大的放右边，然后返回这中间值的位置，下面这函数就是做这个的。

int partition(int n[],int left,int right)
{
int lo,hi,pivot,t;

pivot=n[left];
lo=left-1;
hi=right+1;

while(lo+1!=hi)

{
if(n[lo+1]<=pivot)
lo++;
else if(n[hi-1]>pivot)
hi--;
else

{
t=n[lo+1];
n[++lo]=n[hi-1];
n[--hi]=t;
}
}

n[left]=n[lo];
n[lo]=pivot;
return lo;

}

一个数组和三个指针，第一个指针称为p指针，在整个过程结束之前它牢牢的指向第一个数，第二个指针和第三个指针分别为lo指针和hi指针，分别指向最左边的值和最右边的值。lo指针和hi指针从两边同时向中间逼近，在逼近的过程中不停的与p指针的值比较，如果lo指针的值比p指针的值小，lo++，还小还++，再小再++，直到碰到一个大于p指针的值，这时视线转移到hi指针，如果 hi指针的值比p指针的值大，hi--，还大还--，再大再--，直到碰到一个小于p指针的值。这时就把lo指针的值和hi指针的值做一个调换。持续这过程直到两个指针碰面，这时把p指针的值和碰面的值做一个调换，然后返回p指针新的位置。

#include<iostream>

using namespace std;

int a[200001],n;

void swap(int &a,int &b){

int tmp = a;

a = b;

b = tmp;

}

int partition(int p,int r){

int rnd = rand()%(r-p+1)+p;

swap(a[rnd],a[r]);

int pvt = r, i = p-1;

for(int j = i+1;j<r;j++)

if(a[j]<a[pvt])

swap(a[j],a[++i]);

swap(a[++i],a[pvt]);

return i;

}

void qsort(int p,int r){

if(p<r){

int q = partition(p,r);

qsort(p,q-1);

qsort(q+1,r);

}

}

int main(){

cin>>n;

for(int i=0;i<n;i++)

cin>>a[i];

qsort(0,n-1);

for(int i=0;i<n;i++)

cout<<a[i];

return 0;

}

Tags: 快速, 排序, 算法