201871010202-曹盼盼 软件工程个人项目
| 项目 | 内容 |
|---|---|
| 课程班级博客链接 | 课程班级博客 |
| 这个作业要求链接 | 作业要求 |
| 我的课程学习目标 | 1. 完成所有实验内容。 2. 体验开发一个软件项目的流程，把完成的软件项目发布到Github上。 |
| 这个作业在哪些方面帮助我实现学习目标 | 1. 通过开发一个个人软件工程项目帮助我实现学习目标。 |
1. 实验目的与要求
（1）掌握软件项目个人开发流程。
（2）掌握Github发布软件项目的操作方法。
2. 实验内容
任务1：阅读教师博客“常用源代码管理工具与开发工具”内容要求，点评班级博客中已提交相关至少3份作业。
点评过的博客：201871010203-陈鹏昱 常用源代码管理工具与开发工具
201871030107-常雅伦 常用源代码管理工具与开发工具
201871030135-姚辉 常用源代码管理工具与开发工具
201871030111-胡佳媚 常用源代码管理工具与开发工具
任务2：详细阅读《构建之法》第1章、第2章，掌握PSP流程。
已在课外详细阅读了《构建之法》的第1章和第2章，初步掌握了PSP流程，同时在完成本次实验时亲身经历了PSP流程，并且在实验后附加了PSP流程的具体内容。
个人软件过程(Personal Software Process，PSP)是一种可用于控制、管理和改进个人工作方式的自我持续改进过程，是一个包括软件开发表格、指南和规程的结构化框架。PSP与具体的技术（程序设计语言、工具或者设计方法）相对独立，其原则能够应用到几乎任何的软件工程任务之中。PSP能够说明个体软件过程的原则； 帮助软件工程师作出准确的计划；确定软件工程师为改善产品质量要采取的步骤；建立度量个体软件过程改善的基准；确定过程的改变对软件工程师能力的影响。
任务3：项目开发背景：背包问题（\(Knapsack Problem，KP\)）是\(NP Complete\)问题，也是一个经典的组合优化问题，有着广泛而重要的应用背景。\({ 0-1 }\)背包问题（\({0-1 }Knapsack Problem，{0-1}KP\)）是最基本的KP问题形式，它的一般描述为：从若干具有价值系数与重量系数的物品（或项）中，选择若干个装入一个具有载重限制的背包，如何选择才能使装入物品的重量系数之和在不超过背包载重前提下价值系数之和达到最大？
D{0-1} KP 是经典{ 0-1}背包问题的一个拓展形式，用以对实际商业活动中折扣销售、捆绑销售等现象进行最优化求解，达到获利最大化。D{0-1}KP数据集由一组项集组成，每个项集有3项物品可供背包装入选择，其中第三项价值是前两项之和，第三项的重量小于其他两项之和，算法求解过程中，如果选择了某个项集，则需要确定选择项集的哪个物品，每个项集的三个项中至多有一个可以被选择装入背包，D{0-1} KP问题要求计算在不超过背包载重量 的条件下，从给定的一组项集中选择满足要求装入背包的项，使得装入背包所有项的价值系数之和达到最大；D{0-1}KP instances数据集是研究D{0-1}背包问题时，用于评测和观察设计算法性能的标准数据集；动态规划算法、回溯算法是求解D{0-1}背包问题的经典算法。查阅相关资料，设计一个采用动态规划算法、回溯算法求解D{0-1}背包问题的程序，程序基本功能要求如下：
1.可正确读入实验数据文件的有效D{0-1}KP数据；
2.能够绘制任意一组D{0-1}KP数据以重量为横轴、价值为纵轴的数据散点图；
3.能够对一组D{0-1}KP数据按项集第三项的价值:重量比进行非递增排序；
4.用户能够自主选择动态规划算法、回溯算法求解指定D{0-1} KP数据的最优解和求解时间（以秒为单位）；
5.任意一组D{0-1} KP数据的最优解、求解时间和解向量可保存为txt文件或导出EXCEL文件。
- 需求分析
本次实验的内容是让我们开发一个软件项目，在项目完成后要发布到GitHub上，并且要把项目的运行截图等内容在博客中体现出来。软件项目的开发主要是要掌握背包问题相关的算法，题目还要求实现读数据、绘制散点图、选择解决问题的算法，要有算法设计与分析、数据分析与可视化等课程的内容。
由于导入数据、进行可视化等操作用Python语言处理更加简洁高效，因此在项目中计划采取C++和Python语言设计实现。
功能设计，获得题目需求后，要对项目做功能设计，但题目需求是项目的基本功能要求，自己思考和调研会有超出题目要求的需求，甚至你的奇思妙想会设计出特色的功能。因此，功能会有：
- 基本功能
能够读入数据，能够绘制物品重量与价值的散点图，能够输出求解时间，能够导出运行结果。
- 扩展功能
选择用哪种算法解决0-1背包问题。
设计实现
import numpy as np
def solve(vlist,wlist,totalWeight,totalLength):
resArr = np.zeros((totalLength+1,totalWeight+1),dtype=np.int32)
for i in range(1,totalLength+1):
for j in range(1,totalWeight+1):
if wlist[i] <= j:
resArr[i,j] = max(resArr[i-1,j-wlist[i]]+vlist[i],resArr[i-1,j])
else:
resArr[i,j] = resArr[i-1,j]
return resArr[-1,-1]
if __name__ == '__main__':
v = [0,60,100,120]
w = [0,10,20,30]
weight = 50
n = 3
result = solve(v,w,weight,n)
print(result)
优化以后：
def solve2(vlist,wlist,totalWeight,totalLength):
resArr = np.zeros((totalWeight)+1,dtype=np.int32)
for i in range(1,totalLength+1):
for j in range(totalWeight,0,-1):
if wlist[i] <= j:
resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
return resArr[-1]
if __name__ == '__main__':
v = [0,60,100,120]
w = [0,10,20,30]
weight = 50
n = 3
result = solve2(v,w,weight,n)
print(result)
任务4：完成任务3的程序开发，将项目源码的完整工程文件提交到你注册Github账号的项目仓库中。
已将项目源码的完整工程文件提交到注册的GitHub账号中。
3. 实验总结
这次实验内容多、难度大，需要花费很多时间完成，而且需要用到相关算法的知识以及数据可视化的知识，综合性强，最重要的是让我体验了开发一个软件项目的流程，本次实验收获很多，还有部分设计未能实现，需要继续努力。
| PSP2.1 | 任务内容 | 计划共完成需要的时间(min) | 实际完成需要的时间(min) |
|---|---|---|---|
| Planning | 计划 | 10 | 8 |
| · Estimate | · 估计这个任务需要多少时间，并规划大致工作步骤 | 10 | 8 |
| Development | 开发 | 100 | 120 |
| ·· Analysis | 需求分析 (包括学习新技术) | 6 | 10 |
| · Design Spec | · 生成设计文档 | 5 | 6 |
| · Design Review | · 设计复审 (和同事审核设计文档) | 4 | 6 |
| · Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 3 | 3 |
| · Design | 具体设计 | 10 | 12 |
| · Coding | 具体编码 | 36 | 21 |
| · Code Review | · 代码复审 | 7 | 9 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 13 | 21 |
| Reporting | 报告 | 9 | 6 |
| ·· Test Report | · 测试报告 | 3 | 2 |
| · Size Measurement | 计算工作量 | 2 | 1 |
| · Postmortem & Process Improvement Plan | · 事后总结 ,并提出过程改进计划 | 3 | 3 |
4. 经验分享
本次实验的内容综合性强，需要结合算法、数据可视化以及高级语言课程上学过的知识，还需要花费大量时间去做需求分析，但项目完成以后可以说是收获很多，对于没能完成的地方还需要继续学习，期待以后能够完成。