题意：求一个n*n矩阵的最大子矩阵。
解题思路：类似一维情况下的最大连续子串。
代码：#include <cstdio>

线程是有趣的

了解如何正确运用线程是每一个优秀程序员必备的素质。线程类似于进程。如同进程，线程由内核按时间分片进行管理。在单处理器系统中，内核使用时间分片来模拟线程的并发执行，这种方式和进程的相同。而在多处理器系统中，如同多个进程，线程实际上一样可以并发执行。
那么为什么对于大多数合作性任务，多线程比多个独立的进程更优越呢？这是因为，线程共享相同的内存空间。不同的线程可以存取内存中的同一个变量。所以，程序中的所有线程都可以读或写声明过的全局变量。如果曾用 fork() 编写过重要代码，就会认识到这个工具的重要性。为什么呢？虽然 fork() 允许创建多个进程，但它还会带来以下通信问题: 如何让多个进程相互通信，这里每个进程都有各自独立的内存空间。对这个问题没有一个简单的答案。虽然有许多不同种类的本地 IPC (进程间通信），但它们都遇到两个重要障碍：

• 强加了某种形式的额外内核开销，从而降低性能。
• 对于大多数情形，IPC 不是对于代码的“自然”扩展。通常极大地增加了程序的复杂性。

双重坏事: 开销和复杂性都非好事。如果曾经为了支持 IPC 而对程序大动干戈过，那么您就会真正欣赏线程提供的简单共享内存机制。由于所有的线程都驻留在同一内存空间，POSIX 线程无需进行开销大而复杂的长距离调用。只要利用简单的同步机制，程序中所有的线程都可以读取和修改已有的数据结构。而无需将数据经由文件描述符转储或挤入紧窄的共享内存空间。仅此一个原因，就足以让您考虑应该采用单进程/多线程模式而非多进程/单线程模式。

---

线程是快捷的

不仅如此。线程同样还是非常快捷的。与标准 fork() 相比，线程带来的开销很小。内核无需单独复制进程的内存空间或文件描述符等等。这就节省了大量的 CPU 时间，使得线程创建比新进程创建快上十到一百倍。因为这一点，可以大量使用线程而无需太过于担心带来的 CPU 或内存不足。使用 fork() 时导致的大量 CPU 占用也不复存在。这表示只要在程序中有意义，通常就可以创建线程。
当然，和进程一样，线程将利用多 CPU。如果软件是针对多处理器系统设计的，这就真的是一大特性（如果软件是开放源码，则最终可能在不少平台上运行）。特定类型线程程序（尤其是 CPU 密集型程序）的性能将随系统中处理器的数目几乎线性地提高。如果正在编写 CPU 非常密集型的程序，则绝对想设法在代码中使用多线程。一旦掌握了线程编码，无需使用繁琐的 IPC 和其它复杂的通信机制，就能够以全新和创造性的方法解决编码难题。所有这些特性配合在一起使得多线程编程更有趣、快速和灵活。

---

线程是可移植的

如果熟悉 Linux 编程，就有可能知道 __clone() 系统调用。__clone() 类似于 fork()，同时也有许多线程的特性。例如，使用 __clone()，新的子进程可以有选择地共享父进程的执行环境（内存空间，文件描述符等）。这是好的一面。但 __clone() 也有不足之处。正如__clone() 在线帮助指出：
“__clone 调用是特定于 Linux 平台的，不适用于实现可移植的程序。欲编写线程化应用程序（多线程控制同一内存空间），最好使用实现 POSIX 1003.1c 线程 API 的库，例如 Linux-Threads 库。参阅 pthread_create(3thr)。”
虽然 __clone() 有线程的许多特性，但它是不可移植的。当然这并不意味着代码中不能使用它。但在软件中考虑使用 __clone() 时应当权衡这一事实。值得庆幸的是，正如 __clone() 在线帮助指出，有一种更好的替代方案：POSIX 线程。如果想编写 可移植的 多线程代码，代码可运行于 Solaris、FreeBSD、Linux 和其它平台，POSIX 线程是一种当然之选。

---

第一个线程

下面是一个 POSIX 线程的简单示例程序：

#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
 void *thread_function(void *arg) {
  int i;
  for ( i=0; i<20; i++) {
    printf("Thread says hi!\n");
    sleep(1);
  }
  return NULL;
}
int main(void) {
  pthread_t mythread;
  if ( pthread_create( &mythread, NULL, thread_function, NULL) ) {
    printf("error creating thread.");
    abort();
  }
  if ( pthread_join ( mythread, NULL ) ) {
    printf("error joining thread.");
    abort();
  }
  exit(0);
}

要编译这个程序，只需先将程序存为 thread1.c，然后输入：

$ gcc thread1.c -o thread1 -lpthread

运行则输入：

$ ./thread1

---

理解 thread1.c

thread1.c 是一个非常简单的线程程序。虽然它没有实现什么有用的功能，但可以帮助理解线程的运行机制。下面，我们一步一步地了解这个程序是干什么的。main() 中声明了变量 mythread，类型是 pthread_t。pthread_t 类型在 pthread.h 中定义，通常称为“线程 id”（缩写为 "tid"）。可以认为它是一种线程句柄。

mythread 声明后（记住 mythread 只是一个 "tid"，或是将要创建的线程的句柄），调用 pthread_create 函数创建一个真实活动的线程。不要因为 pthread_create() 在 "if" 语句内而受其迷惑。由于 pthread_create() 执行成功时返回零而失败时则返回非零值，将 pthread_create() 函数调用放在 if() 语句中只是为了方便地检测失败的调用。让我们查看一下 pthread_create 参数。第一个参数 &mythread 是指向 mythread 的指针。第二个参数当前为 NULL，可用来定义线程的某些属性。由于缺省的线程属性是适用的，只需将该参数设为 NULL。

第三个参数是新线程启动时调用的函数名。本例中，函数名为 thread_function()。当 thread_function() 返回时，新线程将终止。本例中，线程函数没有实现大的功能。它仅将 "Thread says hi!" 输出 20 次然后退出。注意 thread_function() 接受 void * 作为参数，同时返回值的类型也是 void *。这表明可以用 void * 向新线程传递任意类型的数据，新线程完成时也可返回任意类型的数据。那如何向线程传递一个任意参数？很简单。只要利用 pthread_create() 中的第四个参数。本例中，因为没有必要将任何数据传给微不足道的 thread_function()，所以将第四个参数设为 NULL。

您也许已推测到，在 pthread_create() 成功返回之后，程序将包含两个线程。等一等， 两个 线程？我们不是只创建了一个线程吗？不错，我们只创建了一个进程。但是主程序同样也是一个线程。可以这样理解：如果编写的程序根本没有使用 POSIX 线程，则该程序是单线程的（这个单线程称为“主”线程）。创建一个新线程之后程序总共就有两个线程了。

我想此时您至少有两个重要问题。第一个问题，新线程创建之后主线程如何运行。答案，主线程按顺序继续执行下一行程序（本例中执行 "if (pthread_join(...))"）。第二个问题，新线程结束时如何处理。答案，新线程先停止，然后作为其清理过程的一部分，等待与另一个线程合并或“连接”。

现在，来看一下 pthread_join()。正如 pthread_create() 将一个线程拆分为两个， pthread_join() 将两个线程合并为一个线程。pthread_join() 的第一个参数是 tid mythread。第二个参数是指向 void 指针的指针。如果 void 指针不为 NULL，pthread_join 将线程的 void * 返回值放置在指定的位置上。由于我们不必理会 thread_function() 的返回值，所以将其设为 NULL.

您会注意到 thread_function() 花了 20 秒才完成。在 thread_function() 结束很久之前，主线程就已经调用了 pthread_join()。如果发生这种情况，主线程将中断（转向睡眠）然后等待 thread_function() 完成。当 thread_function() 完成后, pthread_join() 将返回。这时程序又只有一个主线程。当程序退出时，所有新线程已经使用 pthread_join() 合并了。这就是应该如何处理在程序中创建的每个新线程的过程。如果没有合并一个新线程，则它仍然对系统的最大线程数限制不利。这意味着如果未对线程做正确的清理，最终会导致 pthread_create() 调用失败。

---

无父，无子

如果使用过 fork() 系统调用，可能熟悉父进程和子进程的概念。当用 fork() 创建另一个新进程时，新进程是子进程，原始进程是父进程。这创建了可能非常有用的层次关系，尤其是等待子进程终止时。例如，waitpid() 函数让当前进程等待所有子进程终止。waitpid() 用来在父进程中实现简单的清理过程。

而 POSIX 线程就更有意思。您可能已经注意到我一直有意避免使用“父线程”和“子线程”的说法。这是因为 POSIX 线程中不存在这种层次关系。虽然主线程可以创建一个新线程，新线程可以创建另一个新线程，POSIX 线程标准将它们视为等同的层次。所以等待子线程退出的概念在这里没有意义。POSIX 线程标准不记录任何“家族”信息。缺少家族信息有一个主要含意：如果要等待一个线程终止，就必须将线程的 tid 传递给 pthread_join()。线程库无法为您断定 tid。

对大多数开发者来说这不是个好消息，因为这会使有多个线程的程序复杂化。不过不要为此担忧。POSIX 线程标准提供了有效地管理多个线程所需要的所有工具。实际上，没有父/子关系这一事实却为在程序中使用线程开辟了更创造性的方法。例如，如果有一个线程称为线程 1，线程 1 创建了称为线程 2 的线程，则线程 1 自己没有必要调用 pthread_join() 来合并线程 2，程序中其它任一线程都可以做到。当编写大量使用线程的代码时，这就可能允许发生有趣的事情。例如，可以创建一个包含所有已停止线程的全局“死线程列表”，然后让一个专门的清理线程专等停止的线程加到列表中。这个清理线程调用 pthread_join() 将刚停止的线程与自己合并。现在，仅用一个线程就巧妙和有效地处理了全部清理。

更多资料

下图很好的概括了ClamAV的运行流程。

ClamAV 简介以及适用范围

---

ClamAV是一个在命令行下查毒软件，因为它不将杀毒作为主要功能，默认只能查出您计算机内的病毒，但是无法清除，至多删除文件。ClamAV可以工作很多的平台上，但是有少数无法支持，这就要取决您所使用的平台的流行程度了。另外它主要是来防护一些WINDOWS病毒和木马程序。另外，这是一个面向服务端的软件。

需要反病毒软件？免费么？

---

绝大多数的Linux都是很先进的，所以，很少有病毒能够在linux上运行和繁衍。而且，由于目前PC都使用的是Windows，所以病毒制造者们更愿意去写Windows下的病毒。但是还有很多的原因能致使您使用一些病毒扫描程序的，比如：

• 扫描在您计算机上的Windows设备
• 扫描在本地网络中的Windows计算机
• 扫描您即将要传送给别人的文件
• 扫描您将要发送给别人的EMAIL

ClamAV 安装设置

---

安装ClamAV

这里有两种的ClamAV供您选择 1.手动：安装ClamAV的安装包 2.自动：安装ClamAV-daemon 这两种都可以安装ClamAV，但是要是使用上面的方法，是手动的。 在您安装完成之后，您可能被程序问及一些问题，比如怎么去升级。这就需要您选择一个离您比较近的服务器来升级。ClamAV的升级程序是很小的，所以很值得去自动升级。

怎么使用ClamAV

---

这部分将会介绍安装之后的使用

升级我的病毒库

---

运行 sudo freshclam.
您将会看见以下说明

使用ClamAV扫描我计算机中的文件

---

运行 clamscan.
这里附带一些例子

• 扫描所有用户的主目录就使用 clamscan -r /home
• 扫描您计算机上的所有文件并且显示所有的文件的扫描结果，就使用 clamscan -r /
• 扫描您计算机上的所有文件并且显示有问题的文件的扫描结果， 就使用 clamscan -r --bell -i /
• 当clamAV扫描完所有文件的时候，会显示如下的类似报告

ClamAV只会去扫描对于ClamAV可以读取的文件。 如果您想扫描所有文件，在命令前加上 sudo .

使ClamAV以daemon防护的方式运行

---

安装clamav-daemon就可以了，clamav-daemon将会建立一个名为'clamav'的帐户，这是为了可以使ClamAV扫描一些系统文件，比如您的Email存放的地方，您可以添加'clamav'为这些文件或者目录的所有者。

---

如何知道clamav-daemon是否运行了?

---

查看进程列表就可以了:
如何删除病毒文件？ 在扫描的时候，您可以添加'--remove'
如何知道我现在使用的ClamAV版本？

---

执行 clamscan -V
如何使ClamAV按计划自动运行

---

您可以使用'at'命令来使clamscan和freshclam运行，比如 或者编辑 /etc/crontab 加入以下内容
0 3 * * * root /usr/bin/freshclam --quiet -l /var/log/clamav/clamav.log ＃＃每天3点升级

更多内容请参见Ubuntu中文社区ClamAV专栏。 问题来自于一场“3分钟相亲”活动，参加活动的有n位男士和n位女士。要求每位男士都要和所有的女士进行短暂的单独交流，并为她们打分，然后按照喜欢程度，对每一位女士进行排序；同样的，每位女士也要对所有男士进行打分和排序。
在这之后我们为选择策略为这n位男士和n位女士配对。使得在婚后不会有“出轨”的情况发生。
这里的“出轨”是什么意思：图片来自网络，仅作举例之用

如果以下两种情况之一发生，则会发生出轨：

1. 如果第一对夫妻中的妻子在婚后觉得自己的丈夫没有第二对夫妻中的丈夫帅；第二对夫妻中的丈夫同样也觉得自己的妻子没有第一对夫妻中的妻子漂亮
2. 如果第一对夫妻中的丈夫在婚后觉得自己的妻子没有第二对夫妻中的妻子美；第二对夫妻中的妻子同样也觉得自己的丈夫没有第一对夫妻中的丈夫帅

解决稳定婚姻的算法之一：
延迟认可算法（Gale-Shapley算法）
先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：

1. 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
2. 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。
3. 若某男士被其女友抛弃，重新变成自由男。

在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。
这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。 字典树是一种树形数据结构，他有如下特点：
    每个节点都有固定个数的指向儿子节点的指针，她的儿子某一个节点（如果存在的话）包含的信息就是该节点的下一个字符。
    根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。
例：作为一个简单的演示，这里我们稍微忽略一些细节。下面的这棵树就是一个简单的字典树的例子：

如图所示，如果我们按行存储这些数据：
apple
append
and
antiy
banana
band
我们需要5+6+3+5+6+4=29 B 的空间。
但是字典树只需要20 B 的空间。
这在数据量更大的时候能起到更好的效果。

字典树能够线性时间范围内实现数据的增删改查。

【练习】
2.3-2 MERGE的改进

2.3-5 二分查找的C++代码

*2.3-7 （这道题其实有O(n)的算法，而且写起来更方便些）这里是O(nlogn)的算法
O(nlogn)算法思想：1.首先进行排序；2.然后枚举每一个小于等于x/2的数S[i]，二分查找对应的x-S[i]是否存在

O(n)的方法是在数的范围不是特别大的时候（或者数的范围比较大，此时采用hash的方法）标记的方法，这里假设数的范围<=10000，并且假设数没有重复的情况下，其他情况稍许改变一下就行：

2-4（逆序对）：这道题就是在归并排序中得到逆序对，具体见代码：

（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
即，若n=k*(m+1)，则后取着胜，反之，存在先取者获胜的取法。
n%(m+1)==0. 先取者必败。
（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有
如下三条性质：
1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局势（ ab - ak , ab - ak+ b - ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b - aj 即可。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k（1+√5）/2]，bk= ak + k （k=0，1，2，...,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数（1+√5）/2 = 1。618...,因此,由ak，bk组成的矩形近似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
（三）尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。
计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（^）表示这种运算。这种运算和一般加法不同的一点是1^1=0。先看（1，2，3）的按位模2加的结果：
1 =二进制01
2 =二进制10
3 =二进制11 （^）
———————
0 =二进制00 （注意不进位）
对于奇异局势（0，n，n）也一样，结果也是0。
任何奇异局势（a，b，c）都有a（^）b（^）c =0。
如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b < c,我们只要将 c 变为 a（^）b,即可,因为有如下的运算结果: a（^）b（^）(a（^）b)=(a（^）a)（^）(b（^）b)=0（^）0=0。要将c 变为a（^）b，只要从 c中减去 c-（a（^）b）即可。
获胜情况对先取者进行讨论：
异或结果为0，先取者必败，无获胜方法。后取者获胜；
结果不为0，先取者有获胜的取法。
拓展： 任给N堆石子,两人轮流从任一堆中任取(每次只能取自一堆),取最后一颗石子的人获胜，问先取的人如何获胜？
根据上面所述，N个数异或即可。如果开始的时候T＝0，那么先取者必败，如果开始的时候T>0，那么只要每次取出石子使得T＝0，即先取者有获胜的方法。

题目

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

基本算法

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

复杂度是O(V*Σn[i])。

转化为01背包问题

另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。

但是我们期望将它转化为01背包问题之后能够像完全背包一样降低复杂度。仍然考虑二进制的思想，我们考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。

方法是：将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种物品分成系数分别为1,2,4,6的四件物品。

分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。

这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为<math>O(V*Σlog n[i])的01背包问题，是很大的改进。

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

procedure MultiplePack(cost,weight,amount)     
   if cost*amount>=V         
      CompletePack(cost,weight)         
      return     
   integer k=1     
   while k<amount         
      ZeroOnePack(k*cost,k*weight)         
      amount=amount-k         
      k=k*2     
   ZeroOnePack(amount*cost,amount*weight) 

希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单步执行几次，或者头脑加纸笔模拟一下，也许就会慢慢理解了。

O(VN)的算法

多重背包问题同样有O(VN)的算法。这个算法基于基本算法的状态转移方程，但应用单调队列的方法使每个状态的值可以以均摊O(1)的时间求解。由于用单调队列优化的DP已超出了NOIP的范围，故本文不再展开讲解。我最初了解到这个方法是在楼天成的“男人八题”幻灯片上。

小结

这里我们看到了将一个算法的复杂度由O(V*Σn[i])改进到O(V*Σlog n[i])的过程，还知道了存在应用超出NOIP范围的知识的O(VN)算法。希望你特别注意“拆分物品”的思想和方法，自己证明一下它的正确性，并将完整的程序代码写出来。