201971010111-何晨泽 实验二 个人项目—《{0-1}KP问题》项目报告

任务1：阅读教师博客“常用源代码管理工具与开发工具”内容要求，点评班级博客中已提交相关至少3份作业

• 常用源代码管理工具与开发工具
  

• 点评班级博客

任务2：总结详细阅读《构建之法》第1章、第2章，掌握PSP流程

1. 第一章： 主要讲解了 1.软件=程序+软件工程；2.软件工程的定义

   • 软件=程序+软件工程：
     邹欣老师首先解释了什么是“软件”，什么是“程序”，为我们介绍了软件工程的概念。最后讲述了软件开发的不同阶段，引出了什么是软件工程这个问题。
   • 软件工程的定义：
     软件工程的特殊性：复杂性，不可见性，易变性，服从性，非连续性；
     软件工程的知识领域、软件工程的三大类基础知识领域：计算基础，数学基础和工程基础；
     软件工程的目标：用户满意度，可靠性，软件流程的质量，可维护性。

2. 第二章： 主要讲解了PSP，即Personal Software Process,个人软件开发流程

   • PSP特点：
     • 不局限于某一种软件技术，而是着眼于软件开发的流程。
     • 不依赖于考试，而是依赖工程师自己收集数据，然后分析，提高。
     • 依赖于数据
   • PSP作用：
     PSP可以帮助软件工程师在个人的基础上运用过程的原则，借助于PSP提供的一些度量和分析工具，了解自己的技能水平，控制和管理自己的工作方式，使自己日常工作的评估、计划和预测更加准确、更加有效，进而改进个人的工作表现，提高个人的工作质量和产量，积极而有效地参与高级管理人员和过程人员推动的组织范围的软件工程过程改进。

任务3：项目开发

1. 项目背景：
   {0-1}背包问题：有N件物品和一个容量为M的背包。第i件物品所占空间是w[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大，对于每件物品，仅有取与不取两个状态。

2. 需求分析：
   通过对需求文档进行分析，得到系统有如下模块：

   • 数据读入与处理：
     正确读入实验数据文件的有效{0-1}KP数据，并将其处理为便于后续操作的数据形式。
   • 散点图绘制：
     绘制任意一组{0-1}KP数据以价值重量为横轴、价值为纵轴的数据散点图。
   • 排序：
     对任一组{0-1}KP数据按重量比进行非递增排序。
   • 贪心算法：
     采用贪心算法求解不超过背包容量的最大价值和解向量。
   • 动态规划算法：
     采用动态规划算法求解不超过背包容量的最大价值和解向量。
   • 回溯算法：
     采用回溯算法求解不超过背包容量的最大价值和解向量。
   • 文件保存：
     将求解时间，最大价值，解向量保存至txt文件中。
   • 扩展功能：
     实现背包剩余价值与最大价值之比的比例图绘制，以扇形图的形式呈现。

3. 功能设计：
   根据需求分析，我绘制了如下的功能设计图。
   

4. 设计实现：
   系统运行过程如下。
   

   • 主类 (\(main\))： 包含除扩展功能外其余功能
     • 数据读入与处理
       • 一个 \(ReadFile()\) 函数负责处理数据读入与处理，详细流程如下。
       • 所给数据集的形式较为有序，格式固定。故仅需按照给定格式读入并储存即可。
     • 散点图绘制
       • 一个 \(PlottingScatterPlots()\) 函数负责散点图的绘制，同时需要重写 \(paintComponent()\) 函数。
       • 为确定散点图的边界，还需获取价值和重量的最大值，采用 \(getMaxValue()\) 和 \(getMaxWeight()\) 两个函数获取，以 \(MaxW\) 和 \(MaxV\) 存储。
     • 排序
       • 一个 \(DataSort()\) 函数负责数据的排序，采用了较为基本的冒泡排序方法。同时，为了解决数据交换（Java的数据交换方式与C/C++不同），采用 \(SwapInt()\) 和 \(SwapDouble()\) 两个函数分别实现 \(int\) 类型数据和 \(double\) 类型数据的交换。
     • 贪心、动态规划、回溯
       • 贪心算法用一个 \(Greedy()\) 函数实现，由于在此前已经按照重量比进行了排序，故此处直接使用重量比进行贪心。
       • 动态规划算法用一个 \(DP()\) 函数实现，给出动态转移方程为： \(f[j]=max(f[j], f[j-Weight[i]]+Value[i])\) 。同时，还使用了一个 \(FindPath()\) 函数来获取其解向量。
       • 回溯算法使用了一个 \(BackTrack()\) 函数和一个限界函数（以贪心的思路实现） \(Bound()\) 实现，其详细流程如下。
     • 文件保存
       • 一个 \(WriteFile()\) 函数实现将结果写入txt文件。
   • Addition类：实现扩展功能 (扇形图绘制)
     • 类似的，重写 \(paintComponent()\) 函数用以绘制扇形图。绘制扇形图时需要从主类中传入比例数据。

5. 代码规范：

6. 代码展示：

• 动态规划

f=new int[10010];
for (int i=1;i<=n;i++) {
    for (int j=m;j>=Weight[i];j--) {
        f[j]=Math.max(f[j],f[j-Weight[i]]+Value[i]); //优化后，仅使用一维
    }
}
Res=f[m];

• 散点图绘制

protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2D=(Graphics2D)g;
    g2D.setRenderingHint(RenderingHints.KEY_ANTIALIASING,RenderingHints.VALUE_ANTIALIAS_ON);
    int Width=getWidth();
    int Height=getHeight();
    g2D.draw(new Line2D.Double(Space,Space,Space,Height-Space)); //绘制x轴
    g2D.draw(new Line2D.Double(Space,Height-Space,Width-Space,Height-Space)); //绘制y轴
    Font font=new Font("Microsoft YaHei UI",Font.PLAIN,10); //修改字体
    g2D.setFont(font);
    g2D.drawString("0",Space-10,Height-Space+10); //添加文字
    g2D.drawString("Weight",Width-Space-20,Height-Space+10);
    g2D.drawString("Value",Space-10,Space-5);
    double xAxis=(double)(Width-2*Space)/getMaxWeight();
    double yAxis=(double)(Height-2*Space)/getMaxValue();
    g2D.setPaint(Color.pink);
    for (int i=1;i<=n;i++) { //开始绘制点
        double x=Space+xAxis*Weight[i];
        double y=Height-Space-yAxis*Value[i];
        g2D.fill(new Ellipse2D.Double(x-2,y-2,4,4));
    }
}

• 扩展功能 (扇形图绘制)

protected void paintComponent(Graphics g){
    int CenterX,CenterY;
    int r;
    int Percent=(int)(360*((double)ArcAns/TotalValue)); //计算可容纳所占角度
    CenterX = this.getWidth();
    CenterY = this.getHeight();
    r = this.getWidth()-10;
    super.paintComponent(g);
    g.setColor(Color.pink);
    g.fillArc(5, 10, r, r, 0, Percent); //绘制可容纳部分
    g.setColor(Color.lightGray);
    g.fillArc(5,10,r,r,Percent,360-Percent); //绘制剩余部分
    Font font=new Font("Microsoft YaHei UI",Font.PLAIN,10); //修改字体
    g.setFont(font);
    g.setColor(Color.black);
    g.drawString("粉色：背包可容纳价值",5,300);
    g.drawString("灰色：物品剩余价值",150,300);
}

7. 测试运行
   为便于展示，以第二组数据为例，分别测试贪心、动态规划和回溯的结果。

   • 贪心算法
     
   • 动态规划算法
     
   • 回溯算法
     
   • 文件保存
     

8. 模块化
   设计该项目时，代码规范的核心为可读性，其实现方法为模块化编程。
   具体实现为将不同功能分别写在不同的方法之中，同时如果在某一段方法内其中一段代码重复出现，那么就将该代码再次进行封装，写在一个独立的方法里面，要使用时就进行调用。例如，用于交换数据的 \(SwapInt()\) 和 \(SwapDouble()\) ，即模块化的体现之一。

9. PSP展示

• PSP总结
  总的来说，计划时间与实际时间较为接近，时间误差最大的部分在于具体编码的部分。开始时认为自己对Java的生疏会致使编码时间的增加，后来实际编码过程中并未遇到过大的问题，且在遇到问题时，均通过阅读文档快速解决，故在具体编码方面，计划时间相比实际时间较长。

10. 个人项目总结
    i.{0-1}KP问题：本次项目涉及问题我在高中时期就有过接触，故对于问题的求解和规划便可节省大量时间。本次个人项目也是对此前所学知识的巩固和总结，对于{0-1}KP这一经典问题也有了更深刻的理解。
    ii.项目开发：本次项目是我第一次以软件工程的角度开发，此前虽有项目开发经验，但并未通过PSP等方式规范自己的开发。本次的开发采取了规范流程，对以后的项目开发奠定了基础。
    iii.不足：本次项目的可扩展性较差，还有提高的空间。

任务4：完成任务3的程序开发，将项目源码的完整工程文件提交到你注册Github账号的项目仓库中

按照要求，将完整工程文件提交至项目仓库，命名为201971010111_HCZ_EX2，如下图所示。

1. commit的使用
   本次项目的开发共使用了17次commit，如下图所示。
   

2. issues的使用
   本次项目的开发共发表两条issues，主要用于记录功能及作提示作用，如下图所示。
   

3. release的使用
   本次项目共使用两次realease功能，即发布了两个版本，分别为V1.1和V1.2，如下图所示。