算法设计和分析课程设计报告

课程设计报告要求

1. 题目

01背包问题

给定 N件物品和一个容量V的背包,第a件物品 体积为V 价值为wi,求将那些物品放入背包，可使得物品体积不超过背包容量，且总价值最大。

2. 目的

课程设计的目的是训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。课程设计要求独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的同时，达到如下效果：

（1）深化对算法与数据结构课程中基本概念、理论和方法的理解；

（2）训练综合运用所学知识处理实际问题的能力；

（3）使程序设计与调试水平有一个明显的提高；

（4）培养科学的软件工作方法。

3. 内容

课程设计就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际问题，解决问题的基本步骤是：

1．分析问题，给出数学模型，设计相应的数据结构。

（1）问题建模：分析问题的特点，用数学表达式或其它形式描述其数学模型。用形式模型来刻画问题，将有益于问题的解决。对于形式化的问题，我们容易知道是否有现成的算法或程序可以利用。如涉及到多个对象及相互关系的问题时所用的模型可以为图论；在符号与文本处理问题时常用字符串来做模型。这里《数据结构》课程中所介绍的各种数据结构均可作为一种模型。

（2）选择数据结构

1）选择能够体现问题本身特点的逻辑结构。

2）在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和非顺序存储结构的不同存储方式对算法的时间、空间、性能方面可能有不同的影响，其对应的算法也不相同。除了要能将所需的数据元素及其关系存储起来外，还需要考虑所选择的结构是否便于问题的求解，时间和空间复杂度是否符合要求。

4. 需求分析

1.问题描述：准确的要求编程解决的问题。
给定 N件物品和一个容量V的背包,第i件物品 体积为V 价值为wi,求将那些物品放入背包，可使得物品体积不超过背包容量，且总价值最大。

现在装入背包的物品时，对每种物品i只有两种 选择，即装入背包或者不装入背包。不能将物品i装入背包多次，也不能只装入部分物品i。

2．问题分析

在01背包问题中物体或者被装入背包或者不被装入背包只有两种选择。

在解决问题之前，为描述方便，首先定义一些变量：wi表示第 i 个物品的价值，vi表示第 i 个物品的体积，定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型

2、约束条件

3.确定使用的算法

3.1.动态规划
3.2.回溯法
3.3.分支限界法

3.输入数据
输入背包的容量，物品的体积和价值

输入：

第一行分别是物品的个数和背包总容量

第二行是各个物品的体积，第三行是各个物品的价值

第二行和第三行的数据个数要和物品个数一样

4.输出数据

输出能装入背包的最大价值

比如：

个数：4 背包容量：8

商品的体积为：2 3 4 5

商品的价值为：3 4 5 6

输出：10

读取文件

f = open('F://工作室//造数据//tet.in', 'r')

a = f.readlines()

5. 逻辑结构设计

动态规划：

1. 模块划分：描述所设计程序的各个模块功能。
   

程序入口，将文本数据转换成需要的类型，调用ba()函数

ba() 函数, 动态规划二维运算，将装进背包里的最大价值计算出来

2.主程序的流程以及各个模块之间的调用关系。

1.先将储存在磁盘里的文件数据读取出来，用的是Python语言，一行一行地读取，并且每行数据转换成数组形式。

2. name=='main’程序入口，把文件读取出来的数据分别用n、c、w、v代替

3.ba()函数，传递的参数分别是n、c、w、v，ba函数返回的是最大价值的值

4.sh()函数，传递的参数n,c,w,mmp sh()函数进行动态规划运算

4.然后又回到程序入口__name__==‘main’，输出结果.

回溯法：

2. 模块划分：描述所设计程序的各个模块功能。

程序入口，将文本数据转换成需要的类型，并依次调用backtrack()函数 backtrack(i) 函数 实现回溯法运算，将装进背包里的最大价值计算出来

2.主程序的流程以及各个模块之间的调用关系。

1.先将储存在磁盘里的文件数据读取出来，用的是Python语言，一行一行地读取，并且每行数据转换成数组形式，如果用read()方法，就会一次性把三行数据读取出来。

2.name == 'main’程序入口，把文件读取出来的数据分别用n、c、w、v代替3.backtrack(i)函数，传递的参数是i就是初始值，没用返回值，但里面算出的bestV，bestx等可以在主函数里面直接使用。

4.然后又回到程序入口__name__
== ‘main’：输出结果

6.算法详细设计

动态规划算法

1.动态规划原理和思想

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。

递推逻辑关系式

面对当前商品有两种可能性：

背包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

由此可以得出递推关系式：

j<w(i)
V(i,j)=V(i-1,j)

j>=w(i)
V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝

这里需要解释一下，为什么在能装的情况下，需要这样求解？

可以这么理解，如果要到达V(i,j)这一个状态有几种方式？

肯定是两种，第一种是第i件商品没有装进去，第二种是第i件商品装进去了。没有装进去很好理解，就是V(i-1,j)；装进去了怎么理解呢？如果装进去第i件商品，那么装入之前是什么状态，肯定是V(i-1,j-w(i))。由于最优性原理，V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，才可以得出最优。

二 回溯法

V(i,j)=V(i-1,j)时，说明没有选择第i 个商品，则回到V(i-1,j)；

V(i,j)=V(i-1,j-w(i))+v(i)时，说明装了第i个商品，该商品是最优解组成的一部分，随后我们得回到装该商品之前，即回到V(i-1,j-w(i))；

一直遍历到i＝0结束为止，所有解的组成都会找到。

就拿例子来说吧：

商品的体积为2 3 4 5

商品的价值为：3 4 5 6

背包大小： 8

最优解为V(4,8)=10，而V(4,8)!=V(3,8)却有V(4,8)=V(3,8-w(4))+v(4)=V(3,3)+6=4+6=10，所以第4件商品被选中，并且回到V(3,8-w(4))=V(3,3)；

有V(3,3)=V(2,3)=4，所以第3件商品没被选择，回到V(2,3)；

而V(2,3)!=V(1,3)却有V(2,3)=V(1,3-w(2))+v(2)=V(1,0)+4=0+4=4，所以第2件商品被选中，并且回到V(1,3-w(2))=V(1,0)；

有V(1,0)=V(0,0)=0，所以第1件商品没被选择。

三 分支限界法

基本思想

1.算法的基本思想

非层次遍历

比如：

第一层根结点，左右子结点都满足条件，加入队列；右结点优先级比较高

处理根节点的右结点，它的左右子结点都可以加入，现在队列里面有它父结点的左子结点和它的两个子节点，其中它的左子结点优先级比较高

处理根节点的右子结点的左子结点，两个子节点都可以加入……

基本思想：

① 输入的物品重新排序，按照单位体积价值降序排序

②在一个优先队列里面保存目前待处理的结点，取出的队首元素是值最大的，目前最有 可能成为最优解路径的一部分。

③不断取出队首元素进行处理，考察其左右子结点，满足条件加入优先队列

④不断重复以上③步骤，直到处理的结点是叶子结点，那么它到根节点的路径一定是最优解。

7.编码与调试

编程实现：

动态规划：“

f = open('F://工作室//造数据//tet.in', 'r')
a = f.readlines()
b=len(a)
print(b)
i=0
def ba(n, c, w, v):
   mmp = [[0 for j in range(c + 1)] for i in range(n + 1)] # 置零，表示初始状态
   for i in range(1, n + 1):
      for j in range(1, c + 1):
         if j < w[i - 1]:
            mmp[i][j] = mmp[i - 1][j]
         else:
            mmp[i][j] = max(mmp[i - 1][j], mmp[i - 1][j - w[i - 1]] + v[i - 1]) # 背包总容量够放当前物体，遍历前一个状态考虑是否置换
   return mmp
def sh(n, c, w, mmp):
    print('最大价值为:', mmp[n][c])
    x = [0 for i in range(n)]
    j = c
    for i in range(n, 0, -1):
        if mmp[i][j] >
mmp[i - 1][j]:
            x[i - 1] = 1
            j -= w[i - 1]
    print('背包中所装物品为:')
    for i in range(n):
        if x[i]:
            print('第', i+1, '个,', end='')
    print()
if __name__=='__main__':
    i=0
    k=1;
    while i<b:
        n, c = map(int, a[i].split(' ')) #n是物品个数、c是背包总容量
        w=list(map(int, a[i+1].split(' '))) #w是所有物品的体积
        v=list(map(int, a[i+2].split(' '))) #v是所有物品的价值
        mmp = ba(n, c, w,
v) #value是背包内所装物品的价值
        #print(value)
        print("第一次实验编号：",k)
        print("物品个数及背包总容量分别为：", a[i], end='')
        print("物品的体积分别为：", a[i + 1], end='')
        print("物品的价值分别为：", a[i + 2])
        i+=3
        k+=1
        sh(n, c, w, mmp)

 



回溯法：

```python
f = open('F://工作室//造数据//tet.in', 'r')
a = f.readlines()
b=len(a)
print(b)
i=0
def backtrack(i):
    global bestV, curW, curV, x, bestx
    if i>=n:#约束条件
        if bestV < curV:
            bestV = curV
            bestx = x[:]
    else:
        if curW + w[i] <= c:
            x[i] = True
            curW += w[i]
            curV += v[i]
            backtrack(i + 1)#回溯递归
            curW -= w[i]
            curV -= v[i]
        x[i] = False
        backtrack(i + 1)#回溯递归
if __name__ == '__main__':
    i=0
    k=1;
    while i<b:
        bestV = 0
        curW = 0
        curV = 0
        bestx = None
        n, c = map(int, a[i].split(' ')) #n是物品个数、c是背包总容量
        w = list(map(int, a[i+1].split(' '))) #w是所有物品的体积
        v = list(map(int, a[i+2].split(' '))) #v是所有物品的价值
        #print(value)
        x=[False for i in range(n)]
        print("第一次实验编号：",k)
        print("物品个数及背包总容量分别为：", a[i], end='')
        print("物品的体积分别为：", a[i+1], end='')
        print("物品的价值分别为：", a[i+2])
        k+=1
        backtrack(0)
        i+=3
        print("物品的最大价值：",bestV)
        print(bestx) 
        
1.  算法的时间和空间复杂度的分析。

**动态规划：**

二维耗时

O(N*W)循环二维表中的每一个元素，要么由c[i-1][j]得到，要么

由c[i-1][j-wi]+Vi计算得到，耗时O(1)

关于算法的时间复杂度：O(N*W)

缺点：

算法要求所给的物品的重量Wi是整数；

当背包容量W很大时，算法需要的计算时间比较多，列如：当W>2^{n时，算法需要的时间O(n}2)。

空间复杂度：O(n*C)

回溯法：

时间复杂度：
使用回溯法解决01背包问题时，若可选物品为n个，则其解空间由长度为n的0-1向量组成。
此时时间复杂度为O(2^n)

空间复杂度：

有n个物品，即最多递归n层，存储物品信息就是一个一维数组，即O(n)。

分支限界法：

空间复杂度：限界函数为O(1),最坏情况下需搜索2^(n +１)–２个节点，需O(2^n ) 个空间存储节点，则算法空间复杂性为O(2^n )。

时间复杂度：限界函数时间复杂度为O(n),而最坏情况有2^(n +１) – ２个节点，若 对每个节点用限界函数判断，则其时间复杂度为O(n2^n).而算法中时间复杂度主要依赖
限界函数，则算法的时间复杂度为O(n2^n)。

8. 算法改进，优化方法

动态规划算法的改进

跳跃点算法

函数c[i][j]是关于变量j的接替状单调不减函数

改进步骤

1. 对于每一个确定的i，用一个表p[i]来存储函数c[i][j]的全部跳跃点并按照j升序排序。

2. p[i]可通过计算p[i-1]得到

3. 清除受控点：j大，但价值小的点。

4. 由此可得，在递归地由p[i-1]计算p[i]时，可先由p[i-1]计算出q[i-1]，然后合并p[i-1]和q[i-1]，并清除其中的受控跳跃点得到p[i]

改进后算法的计算时间复杂度为O(min{n*W,2^n})

改进后代码：

def show(objnum,weight,value,jump_points p)：#构造最优解
  vector=[O for x in range(objnum)]
  point=jump points p[5][len(jump_points_p[5])-1]
#是再最优解那么物品就装进去否则就不放
  for i in range(objnum,0,-1):
    temp point=(point[0]-weight[i-1],point[1]-value[i-1])
    if temp_point in jump_points_p[i-1]:
        vector[i-1]=1
        point=temp_point
  return vector
defknapsack improve(weight,alue,capacity):# 
   if len(weight)!=len(value):
    print( parameter err!") " 
    return
obj num=len(weight) 
Jump points p=lfor x in range(obj num+1) #
jump points q=llfor x in range(objnum+1)
Jump points p[o].append((0.0))#00点
for i in range(1.ob)num+1).#物品循环个数
jump_points q[i-1]=[(point[0]+weight[i-1],point[1]+value[i－11)for point in jump points p[i-1]if point[0]+weight[i-1]<=capacity]Jump points pu=merge points(jump_points_p[i-1].、Jump_points_q[i-1])#两个有序的子序列归并成一个有序的子序列
return jump_poinis_p
                                      

9. 测试与结果分析

动态规划：

回溯法：

10.总结，心得体会

对于本次课设，由于我有算法的基础，整个课程设计完成下来是没有遇到太大的问题。不过挺苦脑的是自己一直在想，如何才可以做得更好，不仅仅达到要求，更突出自己的特色。

在一开始实验的时候不知道怎么着手，很烦，总想如何才能做好，但慢慢的做下来，其实认真的去做就是最好的事情。很多时候不要有太多的顾虑，太多犹豫，其实按照自己思考的方向就可以做得很好，哪怕不会也知道如何改进。

其中遇到一些难题，关于文件数据读取，我不太会按行读取，一开始使用C语言编程，最后发现文件读取比较复杂，没搞好，然后用了Python来处理，按行进行就基本没什么问题。