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

湖南理工学院课程**。

**题目 0-1背包问题的设计与实现。

课程名称数据结构与算法设计。

姓名学号。专业班级年级 2014级。

学院计算机学院日期 2023年6月25日。

课程**评价标准。

目录。1. 问题描述3

2. 算法设计分析3

3. 程序编码与调试分析5

4. 测试结果7

5. 自学知识7

6. 课程设计心得体会8

7. 参考文献8

1.问题描述。

给定n种物品和一个背包，物品i的重量是wi，其价值为vi，背包容量为c。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或不装入背包，即不能将物品i装入背包多次，也不能只装入物品i的一部分。

问：如何选择装入背包的物品，使得装入背包中物品的总价值最大？

2.算法设计与分析。

算法分析。在0-1背包问题中，物体被装入一个背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。假设有五个物品，其重量分别是，价值分别是，背包的容量为10。

根据动态规划函数，用一个(n+1)×(c+1)的二维表v，v[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。

按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，v(n,c)便是在容量为c的背包中装入n个物品时取得的最大价值。

为了确定装入背包的具体物品，从v(n,c)的值向前推，如果v(n,c)>v(n-1,c)，表明第n个物品被装入背包，前n-1个物品被装入容量为c-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为c的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。

算法设计。设n个物品的重量存储在数组w[n]中，价值存储在数组v[n]中，背包容量为c，数组v[n+1][c+1]存放迭代结果，其中v[i][j]表示前i个物品装入容量为j的背包中获得的最大价值，数组x[n]存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：

intknapsack(int n, int w[ ]int v[ ]

for (i=0; i<=n; i++)初始化第0列。

v[i][0]=0;

for (j=0; j<=c; j++)初始化第0行。

v[0][j]=0;

for (i=1; i<=n; i++)计算第i行，进行第i次迭代。

for (j=1; j<=c; j++)

if (jelse v[i][j]=max(v[i-1][j], v[i-1][j-w[i]]+v[i]);

j=c; /求装入背包的物品。

for (i=n; i>0; i--)

return v[n][c]; 返回背包取得的最大价值。

3.程序编码与调试分析。

程序编码。#include<>

#include<>

intmax(intx,int y)

for(i=0;i<=n;i++)

for(j=0;j<=c;j++)

printf("%3d ",v[i][j]);

printf("");

printf("背包取得的最大价值：")

printf("%d",v[n][c]);返回背包取得的最大价值。

intmain(){

int n=5,c=10,i;

intv[6][11];

int w[6],v[6];

for(i=1;i<6;i++)

scanf("%d",&w[i]);

for(i=1;i<6;i++)

scanf("%d",&v[i]);

knapsack(5,10,w,v,v);

调试分析。以上0-1背包问题的**的时间复杂度为o(nc).（n表示物品的总数，c为重量限制背包容量），当背包容量c很大时，算法需要的计算时间比较多。

动态规划依赖于上一个或者上一行的解，所以我常在输出子序列的时候出现问题，这源自于对动态规划的知识不是很了解。

4.测试结果。

5.自学知识。

在这个程序设计中，涉及了动态规划，动态规划是解决多阶段决策问题常用的最优化理论，其基本思想是沿着决策的阶段划分自问题，决策的阶段可以随时间划分，也可以随着问题的转换状态划分。

设计动态规划算法，通常可按照以下几个步骤进行：

1）找出最优解的性质，并刻画其结构特征。

2）递归地定义最优解的值。

3）以自底而上的方式计算出最优值。

4）根据计算最优值时得到的信息，构造一个最优解。

6.课程设计心得体会。

动态规划依赖于上一个或上一行的解，这次实验总是在输出子序列的时候出现问题，本来动态规划的知识没有学好，正好在最后的课程设计选0-1背包问题作为实验对象，完完整整的通过这次设计对0-1背包问题和动态规划都有了很深刻的了解，这有助于以后我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。

7.参考文献。

1] 谭浩强等。《c语言程序社会》，清华大学出版社，2013.

2] 王晓华等。《算法的乐趣》，人民邮电出版社， 2015.

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

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

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

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

其他用户还读了