为什么有的书上面称之为背包（算法（第四版））

Answer 1

liuyubobobo 2018-08-17 02:20:33

背包这个叫法是一个抽象数据结构的称呼。在这个课程的后续，你还将看到集合和映射两种非常重要的抽象数据结构，就会更深刻的理解什么是抽象数据结构。他们通常表示定义了一些列操作的接口，但是对底层的实现不做限制。你可以使用动态数组实现，也可以使用链表实现，还可以使用二分搜索树红黑树AVL树去实现。其实，队列和栈也是抽象数据结构，你很快就能学习到。

背包这种抽象数据结构，通常指可以存储若干元素的结构，而且在这种结构上通常不定义删除操作。这种抽象结构用于入门时理解什么是数据结构或许是有帮助的，但实际上，由于它本身是“集合”这种抽象数据结构的子集，所以实际中。近乎没有任何一个标准库中会有Bag这种数据结构：）

而动态数组则是更为标准的一种顺序表的底层实现机制（另一种是链表）。你可以非常轻易的使用动态数组封装一个Bag（依然是，对这种封装理解不深刻没有关系，在课程后续将栈，队列，集合和映射的时候，就会讲到）。无论是C++语言STL中的vector类，还是Java语言的ArrayList，本质就是动态数组。（关于ArrayList，在本章最后会提及：）

算法4中的介绍，本质是使用动态数组的底层实现，实现了一个背包这种抽象数据结构。但由于算法4没有包装动态数组这种基础的底层实现，你将会看到在其实现栈和队列时，包括实现堆时，无法复用动态数组的代码：）届时可以再比较一下：）

加油！

• 提问者 慕数据2731144 #1

  额，读了那么多年，背包这个概概念一直被我所误解。。

• liuyubobobo 回复 提问者 慕数据2731144 #2

  没关系的，这个抽象数据结构，用处不多的。其实就是表示一个袋子，可以往里扔元素：）当然，这和“背包问题”中的“背包”，是两回事儿哦：）