201871010126 王亚涛 实验三 结对项目—《D{0-1}KP 实例数据集算法实验平台》项目报告

项目	内容
课程班级博客	班级博客
这个作业要求链接	作业要求
我的课程学习目标	1、通过阅读《现代软件工程—构建之法》第3-4章内容，掌握了风格规范、代码设计规范、代码复审、结对编程概念； 2、在上一次了解了Github的基础上，再次熟悉了Github发布软件项目的操作方法。 3、通过结对编程的训练，让我在结对伙伴身上学到了很多技术与能力，学到了对方身上的优点
这个作业在哪些方面帮助我实现学习目标	1、再次接触了PSP流程，对个人软件项目开发流程的特点和基础在掌握的基础上有了更深入的了解； 2、了解了Github发布软件项目的操作方法。 3、通过自己学习了遗传算法，通过实验任务对背包问题再次掌握，并学会使用相关算法解决背包问题 4、通过和结对伙伴的交流与合作让我学习到了对方身上在项目设计过程中的优点
结对方学号-姓名	201871010126—王方
结对方本次博客作业链接	https://www.cnblogs.com/wf-001128/p/14620663.html
项目Github的仓库链接地址

博客正文

• 任务1：阅读《现代软件工程—构建之法》第3-4章内容，理解并掌握代码风格规范、代码设计规范、代码复审、结对编程概念；

  • 代码风格规范：
    代码风格的原则是：简明，易读，无二义性。

  • 代码设计规范：
    编码规范、命名规范、个性规范、注释规范、排版规范等
    编码规范:命名规范定义这个规范的目的是让项目中所有的文档都看起来像一个人写的，增加可读性，减少项目组中因为换人而带来的损失。（这些规范并不是一定要绝对遵守，但是一定要让程序有良好的可读性）
    注释规范:定义这个规范的目的是让项目中所有的文档都看起来像一个人写的，增加可读性，减少项目组中因为换人而带来的损失。

  • 代码复审：指对计算机源代码系统化地审查，常用软件同行评审的方式进行，其目的是在找出及修正在软件开发初期未发现的错误，提升软件质量及开发者的技术。代码审查常以不同的形式进行，例如结对编程、非正式的看过整个代码，或是正式的软件检查。

  • 结对编程：两位程序员肩并肩地坐在同一台电脑前合作完成同一个设计。同一个算法、同一段代码或同一组测试、与两位程序员各自独立工作相比．结对编程往往只需花费大约一半的时间就能编写出质量更高的代码， 但是，人与人之间的合作不是一件简单的事情——尤其当人们都早已习惯了独自工作的时候、实施结对编程技术将给软件项目的开发工作带来好处．只是这些好处必须经过缜密的思考和计划才能真正体现出来。而另一方面，两个有经验的人可能会发现配对编程里没有什么技能的转移，但是让他们在不同的抽象层次解决同一个问题会让他们更快地找到解决方案，而且错误更少。

• 任务2
  对结对对方博客评论链接如下：实验二评论
  评论截图如下：
  

• 任务3
  博文作为任务3结对编程任务总结的文字资料，需完整包含以下内容：

• 需求分析陈述。

  • 汉堡包法：最外层: 行为和后果
    中间层: 习惯和动机
    最内层: 本质和基本属性
  • 陈述：为更好地满足D{0-1}KP 实例数据集算法需求，设计实现了设计开发一款D{0-1}KP 实例数据集算法实验，可以支持D{0-1}KP 实例数据集需存储在数据库、平台可动态嵌入任何一个有效的D{0-1}KP 实例求解算法，并保存算法实验日志数据；人机交互界面要求为GUI界面（WEB页面、APP页面都可）等基础功能；该实验平台可以帮助我们理解经典算法的设计思想，设计策略，时空复杂性以及实现过程，使我们更好地掌握软件工程的教学内容，提高课堂教学效率和我们的自学创新能力。

• 软件设计说明。

  • 采用两人结对编程方式，设计开发一款D{0-1}KP 实例数据集算法实验平台，使之具有以下功能：
    （1）平台基础功能：实验二 任务3；
    （2）D{0-1}KP 实例数据集需存储在数据库；
    （3）平台可动态嵌入任何一个有效的D{0-1}KP 实例求解算法，并保存算法实验日志数据；
    （4）人机交互界面要求为GUI界面（WEB页面、APP页面都可）；
    （5）查阅资料，设计遗传算法求解D{0-1}KP，并利用此算法测试要求（3）；
    • 遗传算法：
      1、遗传算法的基本思想
      遗传算法的搜索从一个被称作种群的候选解集开始，新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解；适
      应度越大，解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。
      2、遗传算法的基本元素。
      遗传算法由以下几个原素组成：由染色体组成的种群，根据适应度进行选择以及交叉产生后代。
      3、解决思路
      利用遗传算法时，可以随机生成一个长度为50的0-1序列，其中1表示对应位置的物品装进背包，0表示对应物品不装进背包，需要注意的是，生成的序列有可 能 ，超过背包的总重量，不满足约束条件，此时需要对序列进行操作。可行的操作有两种，第一种是对于不满足约束条件的序列进行抛弃，第二种是对其进行贪心算子变换，具体操作如下：
      a.对所有 x_1=1 的物品，按它们的价值密度排序，形成队列b(i)；
      b.依次放入价值密度最大的物品，并判断是否有超出背包限定的范围；
      c.如果超出，则将价值密度序列中从这个位置之后的所有商品置0；
      4、编程设计
      • 类的设计：

`

class Global {

  publicfinal static int M =200;                                       //种群的规模

  publicfinal static int T = 1000;                                     //遗传的最大代数

  publicfinal static double pc = 0.8;                      //交叉率

  publicfinal static double pv = 0.05;                   //变异率

        } 
class MaxValue{

  publicstatic int[] have = null;                     //最大解选择到的物品

  publicstatic int max_value = 0;                          //最大解的价值

          }
public class GasolvePackage`

• 类的功能

Global类中定义的相当于全局变量。

MaxValue类中记录最优解，have数组记录选择的到的物品，max_value记录最优解得价值

GasolvePackage类有遗传算法的各种函数

• 代码及注释

`

import java.io.*;

import java.util.*;

classMaxValue{

  publicstatic int[] have = null;                     //最大解选择到的物品

  publicstatic int max_value = 0;                          //最大解的价值

}

classGlobal {

  publicfinal static int M =200;                                       //种群的规模

  publicfinal static int T = 1000;                                     //遗传的最大代数

  publicfinal static double pc = 0.8;                      //交叉率

  publicfinal static double pv = 0.05;                   //变异率

}

public class GasolvePackage {

privateint package_rj = 0;                                                      //背包的容量

privateint num = 0;                                                         //物品的个数

privateint[]tiji = null;                                                      //物品的容积

privateint[]value = null;                                                 //物品的价值

privateint[][] zq = null;

publicGasolvePackage(){

        try{

    BufferedReaderread=new BufferedReader(new InputStreamReader(newFileInputStream("input.txt")));

    Stringa=new String();

    Stringb=new String();

    package_rj=Integer.parseInt(read.readLine().trim());

a=read.readLine();

tiji=strArr_to_intArr(a.split(""));   

b=read.readLine();

value= strArr_to_intArr(b.split(" "));

num=value.length;

MaxValue.have=newint[Global.M];

read.close();

}

catch(Exceptione)

{

System.out.println("请检查输入文件中的错误");
}

}


privateint[] strArr_to_intArr(String[] strArr){

intsize = strArr.length;

int[]int_arr = new int[size];

for(inti = 0; i < size; i ++){

int_arr[i]= Integer.valueOf(strArr[i]);

              }

    returnint_arr;
}

privateint[][] dCopy(int[][] source){ //二维数组的复制

introw_num = source.length;

intcol_num = source[0].length;

int[][]des = new int[row_num][col_num];

    for(inti = 0; i < row_num; i ++)

    for(intj = 0; j < col_num; j ++){

        des[i][j]= source[i][j];
    }
          }

    returndes;
}

//产生初始种群

publicint[][] init(){

Randomrand=new Random();

    zq= new int[Global.M][num];

    for(inti = 0; i < Global.M; i ++){

    for(intj = 0; j <num; j ++){

        zq[i][j] = rand.nextInt(2);            
                    }

//产生初始种群

publicint[][] init(){

    Randomrand=new Random();

    zq= new int[Global.M][num];

        for(inti = 0; i < Global.M; i ++){

            for(intj = 0; j <num; j ++){

                zq[i][j] = rand.nextInt(2);
                  }
    if(get_singleWeight(zq[i])> package_rj){

            i--;    
                }
                    }
returnzq;
              }

//计算个体的总重量

privateint get_singleWeight(int[] single){

inttotal_weight = 0;

intsize = single.length;

    for(inti = 0; i < size; i ++){

        total_weight+= tiji[i]*single[i];

            }

              returntotal_weight;

        }

//计算个体的总价值

privateint get_singleValue(int[] single){

inttotal_value = 0;

intsize = single.length;

for(inti = 0; i < size; i ++){

      total_value+= value[i]*single[i];

            }

        returntotal_value;

          }

//获取总价值最大的个体

publicvoid get_maxValue_single(int[][] popu){

intsize = popu.length;

int[]fitness = new int[size];

for(inti = 0; i < size; i ++)

    fitness[i]= get_singleValue(popu[i]);
        }
        
intid = 0;
intmax_value = fitness[0]
for(intj = 1; j < size; j ++){
    if(fitness[j]> max_value){

        max_value= fitness[j];
        
            id= j;

            }
    }

        if(max_value> MaxValue.max_value){

            MaxValue.max_value= max_value;

            int[]have = new int[num];

            for(inti = 0; i < num; i ++){

        have[i]= popu[id][i];

                }
                    MaxValue.have= have;
}
    }

//遗传算法

publicvoid allway(){
    intpopu_id = 1;        //总群的代数

    double[]fitness = null;

    double[]select_rate = null;

    double[]accu_rate = null;

    int[][]select_popu = null;

    int[][]cross_popu = null;

    int[][]popu = init();

    get_maxValue_single(popu);

    while(popu_id< Global.T){//没有终止

    fitness= getFitness(popu);

    select_rate= get_selectRate(fitness);
    accu_rate= get_accuRate(select_rate);
    select_popu= select(accu_rate, popu);
    cross_popu= crossover(select_popu);
    popu= variation(cross_popu);
  //下一代总群
    opu_id++;
    get_maxValue_single(popu);
        }
}

//输出

publicvoid show(){

    System.out.print("背包容积：");
    System.out.println(package_rj);
    System.out.print("选择物品的体积：");
    for(intj = 0; j < num; j ++){
        if(MaxValue.have[j]== 1){
              System.out.print(tiji[j]+ " ");
          }
    }

    intMaxHeight=0;

    for(inti=0;i<num;i++)

    MaxHeight+=MaxValue.have[i]*tiji[i];

    System.out.println();

    System.out.print("选择物品的总体积：");

    System.out.println(MaxHeight);

    System.out.print("选择物品的价值：");

    for(intj = 0; j <num; j ++){
    if(MaxValue.have[j]== 1){
        System.out.print(value[j]+ " ");
          }
}
        System.out.println();
        System.out.print("物品的总价值：");
        System.out.print(MaxValue.max_value);
}
publicstatic void main(String[] args){
GasolvePackagega = new GasolvePackage();
    ga.allway();
    ga.show();
    }
}` 

（6）附加功能：除（1）-（5）外的任意有效平台功能实现。

• 描述结对的过程，提供两人在讨论、细化和编程时的结对照片(非摆拍)。
  
• 供此次结对作业的PSP。
  PSP如下：

• 展示PSP：
  • PSP设计过程：
    PSP设计中的4个因素:
    1、项目/任务大小（代码行数）：430
    2、花的时间(min）：2830
    3、质量如何：代码在结对编程的过程中遇到的问题较多
    4、是否按时交付：按时交付

PSP 各个阶段	自己预估的时间（min）	实际的记录（min）
计划: 明确需求和其他因素，估计以下的各个任务需要多少时间
开发	预估时间	实际开发时间
需求分析	400	450
生成设计文档	90	120
设计复审	200
代码规范	260	200
具体设计	540	600
具体编码	540	500
代码复审	60	80
测试	60
报告	60	50
测试报告（发现了多少bug，修复了多少）	240	390
事后总结, 并提出改进计划 （包括写文档、博客的时间）	120	120
总共花费的时间 （min）	2570	2750

• 小结感受：两人合作真的能够带来1+1>2的效果吗？通过这次结对合作，请谈谈你的感受和体会。
  两人合作真的能够带来1+1>2的效果,通过这次结对合作，我的感受和体会：在这次项目过程中再次加入了结对编程的措施，在结对编程的过程中我们从结对伙伴对象身上学习到了许多，在解决问题的过程中也少了许多的错误，互相鼓励，不容易沮丧，互相监督，不容易偷懒：两个人一起工作需要互相配合，如果想偷懒去干别的，就会拖延工作进度，在编程中，相互讨论，可以更快更有效地解决问题，互相请教对方，可以得到能力上的互补，在这次编程互相学到了很多，发现了彼此身上一些知识面的不足以及知识掌握的缺失，但也看到了彼此身上某个知识面的深入，以后还会互相学习的。