#include\

#define N 6 /*物品数量*/ #define S 8 /*背包大小*/

int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/

/*

背包函数 knapsack() 参数

int s 剩余重量 int n 剩余物品数

返回 int 背包分配是否成功 */

int knapsack(int s,int n) { if(s == 0)/*分配结束，成功*/

return 1;

if(s < 0 || (s > 0 && n < 1))/*没有可用空间，或者物品分配完毕*/ return 0;

if( knapsack(s - W[n] , n - 1)){/*递归*/ printf(\/*输出*/

return 1;

}

return knapsack(s , n - 1);

}

int main() { if(knapsack(S , N))/*递归调用*/

printf(\else printf(\

return 1; }/*main*/

非递归解法：

一件一件的物品往包（即栈）里放，发现有问题，拿出来，放其他的物品。 （1）i=1

（2）从第i件到第n件测试每件物品，对于第j次循环，测试第j件物品

（2.1）如果该物品可以放，入栈

（2.2）若栈的容量刚好达到要求，成功，打印栈元素。 （2.3）继续测试j+1件物品

（3）若没有成功

（3.1）若栈空，返回失败

（3.2）将栈顶物品（设第k个）出栈 （3.3）令i=k+1，返回（2）

代码：

#include\

#define N 6 /*物品数量*/ #define S 8 /*背包大小*/

int W[N+1]={0,1,2,3,4,5,6};/*数据，各物品重量，W[0]不使用*/ int stack[1000]={0}; int value=0; int size=0;

knapsackstack() { int i=1; }

while (1) { for (int j=i;j<=N;j++) }

{

if (value+W[j]<=S) {stack[size++]=j; value+=W[j];} if (value==S){ printf(\得到一组解：\ }

for (int p=0;p

else if (value>S) break; }

if (size==0) {printf(\i=stack[--size]+1; value-=W[i-1];

void main() { }

knapsackstack();

习题4

1. 填空题

（1）一般来说，数组不执行（___________）和（___________）操作，所以通常采用

（___________）方法来存储数组。通常有两种存储方式：（___________）和（___________）。 答案：删除 插入 顺序存储 行优先存储 列优先存储

（2）设8行8列的二维数组起始元素为A[0][0]，按行优先存储到起始元素下标为0的一维数组B中，则元素B[23]在原二维数组中为（___________）。若该二维数组为上三角矩阵，按行优先压缩存储上三角元素到起始元素下标为0的一维数组C中，则元素C[23]即为原矩阵中的（___________）元素。 答案：A[2][7] A[3][5]

（3）设二维数组A为6行8列，按行优先存储，每个元素占6字节，存储器按字节编址。已知A的起始存储地址为1000H，数组A占用的存储空间大小为（___________）字节，数组A的最后一个元素的下标为（___________），该元素的第一个字节地址为（___________）H，元素A[1][4]的第一个字节的地址为（___________）H。（提示：下标从0开始计） 答案：288 A[5][7] 111AH 1048H

（4）设C++中存储三维数组Amnp，则第一个元素为a000，若按行优先存储，则aijk前面共有（___________）个元素；若按列优先存储，则aijk前面共有（___________）个元素。 答案：inp+jp+k i+mj+mnk

（5）常见的稀疏矩阵压缩方法有：（___________）和（___________）。

答案：三元组表 十字链表 （6）广义表（（a），（（b，c），d），（e））的长度为（___________），表头为（___________），表尾为（___________）。 答案：3 （a） （（（b，c），d），（e）） （7）设广义表LS＝（（a），（（b，c），d），（e）），若用取表头操作GetHead（）和取表尾操作GetTail（）进行组合操作，则取出元素b的运算为（___________）。 答案：GetHead(GetHead(GetHead(GetTail(LS))))

（8）若广义表A满足GetHead（A）＝GetTail（A），则A＝（___________）。 答案：（（））

2. 问答题

（1）根据下面的矩阵，写出矩阵转置后的三元组表，起始行列值为1。

?0??0??3??0?0??15?12000180900130000000005000000140000??0?0?? 0??0?0?? Row 1 1 2 2 3 Col 3 6 1 5 1 Item -3 15 12 18 9 3 5 6 矩阵行数：7 矩阵列数：6 4 2 3 13 5 14 非零元素个数：8

（2）对于如下稀疏矩阵，请写出对应的三元组顺序表，若采用顺序取，直接存的算法进行转置运算，引入辅助数组number[]和position[]，分别表示矩阵各列的非零元素个数和矩阵中各列第一个非零元素在转置矩阵中的位置，请写出数组中的各元素（所有数组起始元素下标为0）。 ?0??3 原矩阵 ?0??0?000020?100??0? 5??0??

Row 0 1 2 2 行数：4 Col 2 0 2 3 Item 2 3 -1 5 Col Number[col] Position[col] 0 1 0 1 0 1 2 2 1 3 1 3 列数：4 非零元素个数：4

（3）对于上题中的稀疏矩阵，写出对应的三元组表和十字链表。

三元组表： Row 0 1 Col 2 0 Item 2 3