| 项目 | 内容 |
|---|---|
| 课程班级博客链接 | 班级博客 |
| 这个作业要求链接 | 作业要求 |
| 我的课程学习目标 | 1.掌握软件项目个人开发流程。 2.掌握Github发布软件项目的操作方法。 |
| 这个作业在哪些方面帮助我实现学习目标 | 1.通过阅读《构建之法》初步了解PSP流程 2.通过使用Github了解Github的基本操作。 3.通过任务3的项目开发，对软件工程有了进一步认识了解 |
| 项目Github的仓库链接地址 | 仓库地址 |
- 任务1：阅读教师博客“常用源代码管理工具与开发工具”内容要求，点评班级博客中已提交相关至少3份作业。
- 任务2：详细阅读《构建之法》第1章、第2章，掌握PSP流程，
- 已按任务要求完成
- 任务3：项目开发背景：背包问题（Knapsack Problem，KP）是NP Complete问题，也是一个经典的组合优化问题，有着广泛而重要的应用背景。{０-1}背包问题（{0-1 }Knapsack Problem，{0-1}KP）是最基本的KP问题形式，它的一般描述为：从若干具有价值系数与重量系数的物品（或项）中，选择若干个装入一个具有载重限制的背包，如何选择才能使装入物品的重量系数之和在不超过背包载重前提下价值系数之和达到最大？
1. 需求分析，即使老师已经给出了题目，也要对题目的需求做分析。（5分）
背包问题(knapsack problem, KP)是一个经典的组合优化问题，有着广泛的实际应用背景，如预算控制、项目选择、材料切割和货物装载等，背包问题可以描述为：有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
举例：number＝4，capacity＝8
| i（物品编号） | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w（体积） | 2 | 3 | 4 | 5 |
| v（价值） | 3 | 4 | 5 | 6 |
- 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。
- 动态规划的原理：动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。
- 最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。
2. 功能设计，获得题目需求后，要对项目做功能设计，但题目需求是项目的基本功能要求，自己思考和调研会有超出题目要求的需求，甚至你的奇思妙想会设计出特色的功能。因此，功能会有： 基本功能（5分） 扩展功能（若代码实现，附加10分）
- 基本功能：运用动态规划的原理找出背包问题的最优解。
- 扩展功能：背包问题最优解回溯：求出背包问题的最优解，但还不知道这个最优解由哪些商品组成，故要根据最优解回溯找出解的组成。
3. 设计实现，设计包括你会有哪些类，这些类分别负责什么功能，他们之间的关系怎样？你会设计哪些重要的函数，关键的函数是否需要画出流程图？函数之间的逻辑关系如何？（10分）
重要的函数：findmax()函数，返回数组中最大值元素的下标，解决动态规划问题。
具体设计实现：定义一些变量：Vi表示第i个物品的价值，Wi表示第i个物品的体积，定义V(i,j)：当前背包容量j，前i个物品最佳组合对应的价值，同时背包问题抽象化（X1，X2，…，Xn，其中Xi取0或1，表示第i个物品选或不选）。
1、建立模型，即求max(V1X1+V2X2+…+VnXn)；
2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；
3、寻找递推关系式，面对当前商品有两种可能性：
包的容量比该商品体积小，装不下，此时的价值与前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(0,j)=V(i,0)=0；
| i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | ||||||||
| 2 | 0 | ||||||||
| 3 | 0 | ||||||||
| 4 | 0 |
然后一行一行的填表：
如，i=1，j=1，w(1)=2，v(1)=3，有j<w(1)，故V(1,1)=V(1-1,1)=0；
又如i=1，j=2，w(1)=2，v(1)=3，有j=w(1),故V(1,2)=max｛ V(1-1,2)，V(1-1,2-w(1))+v(1) ｝=max｛0，0+3｝=3；
如此下去，填到最后一个，i=4，j=8，w(4)=5，v(4)=6，有j>w(4)，故V(4,8)=max｛ V(4-1,8)，V(4-1,8-w(4))+v(4) ｝=max｛9，4+6｝=10……
所以填完表如下：
| i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 | 7 | 7 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 9 |
| 4 | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10 |
由表格得：最优解即是V(number,capacity)=V(4,8)=10。
4. 测试运行，你的项目必须是可运行的，请展示项目代码的运行截图，包括题目要求实现功能对应的运行截图。这些截图说明你确实完成了项目需求，如果实现了扩展需求，也请大方秀出来。（5分）
运行结果：
扩展需求：
求出背包问题的最优解，根据回溯知道这个最优解由第三个和第五个商品组成的。
5. 粘贴自己觉得比较独特的或满意的代码片段，用博客园的代码控件来显示。（提示：要有必要的注释说明，提示：不要贴所有代码！不符合规定的要倒扣分）（5分）
void findMax() { //动态规划 for (int i = 1; i <= 4; i++) { for (int j = 1; j <= bagV; j++) { if (j < w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } } }
void findWhat(int i, int j) { //最优解情况 if (i >= 0) { if (dp[i][j] == dp[i - 1][j]) { item[i] = 0; findWhat(i - 1, j); } else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) { item[i] = 1; findWhat(i - 1, j - w[i]); } } }
6. 总结：你设计的程序如何实现软件设计的“模块化”原则。（5分）
- 对问题进行需求分析，将问题划分成两个模块，第一个模块运用动态规划的原理找出背包问题的最优解，第二个模块则根据最优解回溯找出解的组成，第一个模块是第二个模块的基础，在实现第一模块后在对第二模块设计实现，在程序设计中要加上第三个模块：输出模块，包括动态规划表的输出与最优解情况的输出。
7. 展示PSP，这个环节重要的是让自己看到自己的估计和实际消耗时间，哪个环节耗时最多，哪个环节估计和实践相差巨大？为什么？（5分）
| PSP2.1 | 任务内容 | 计划共完成需要的时间(h) | 实际完成需要的时间(h) |
|---|---|---|---|
| Planning | 计划 | 1 | 1 |
| Estimate | 估计这个任务需要多少时间，并规划大致工作步骤 | 1 | 0.5 |
| Development | 开发 | 5 | 7 |
| Analysis | 需求分析 (包括学习新技术) | 2 | 1 |
| Design Spec | 生成设计文档 | 1 | 2 |
| Design Review | 设计复审 (和同事审核设计文档) | 1 | 2 |
| Coding Standard | 代码规范 (为目前的开发制定合适的规范) | 1 | 1 |
| Design | 具体设计 | 2 | 3 |
| Coding | 具体编码 | 4 | 6 |
| Code Review | 代码复审 | 1 | 1 |
| Test | 测试（自我测试，修改代码，提交修改） | 2 | 3 |
| Reporting | 报告 | 2 | 1 |
| Test Report | 测试报告 | 2 | 2 |
| Size Measurement | 计算工作量 | 1 | 1 |
| Postmortem & Process Improvement Plan | 事后总结 ,并提出过程改进计划 | 1 | 1 |