数据结构课外实验报告

1背包问题 1.1问题描述

假设有一个能装入总体积为T的背包和n件体积分别为w1,w2,…wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wm=T，要求找出所有满足上述条件的解。

例如：当T=10，各件物品的体积{1,8,4,3,5,2}时，可找到下列4组解： (1,4,3,2) (1,4,5) (8,2) (3,5,2)

1.2算法设计

利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后，顺序选取物品装入背包，若已选取第i件物品后未满，则继续选取第i+1件，若该件物品“太大”不能装入，则弃之，继续选取下一件，直至背包装满为止。

如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入的物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直到求得满足条件的解，或者无解。

由于回溯求解的规则是“后进先出”，自然要用到“栈”。

同时，因为要使用回溯法，所以采取一个data数组来记录入栈的数据在原本的数组中的位置信息，从而可以保证回溯时回溯到恰当的位置之上。

1.3源代码

// beibao.cpp : 定义控制台应用程序的入口点。 #include \ #include #define size 20 using namespace std; class stacks { public:

int data[size]; int top;

}stack; int main() {

int w[size]; int v; int k=0; int j=1; int number; int s=0;

cout<<\<

cin>>number;

cout<<\<

cout<<\<>v; If(v<0||v>s) do { }

while(!(stack.top==0&&k==number)); getchar();

while(v>0&&k

--stack.top;

k=stack.data[stack.top]; stack.data[stack.top]=0; v+=w[k]; k++;

cout<<\<

cout<=w[k]) { } k++;

stack.data[stack.top]=k; stack.top++; v-=w[k];

cout<<\<

cin>>w[i]; s=s+w[i];

}

return 0;

1.4运行结果

2农夫过河问题 2.1问题描述

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。

2.2算法设计

求解这个问题的简单方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择后再考虑下一步的各种方案。要模拟农夫过河问题，首先需要对问题中的每个角色的位置进行描述。可用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表在南岸，1表示在北岸。例如，整数5 (0101)表示农夫和白菜在南岸，而狼和羊在北岸。

现在问题变成：从初始的状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标。总状态共16种(0000到1111)，(或者看成16个顶点的有向图)可采用广度优先或深度优先的搜索策略---得到从0000到1111的安全路径。

首先用一个函数来保证这16种状态之中是否是安全的，可以知道，其中的十种情况是安全的，将其记录下来。然后，再设计另一个函数，来判断其中的两种状态是否可以在一步中完成，如果可以返回1，不可以返回0。就可以通过这样的方式建立一个十乘十的邻接矩阵，如果两种状态可以一步完成，那么就在邻接矩阵中的恰当位置添上1，否则不变，仍旧