北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java

### 学生信息 0. 学号： ### 编程语言 Java ### 运行环境 0. jdk1.8以上（1.8版本以下会报错） 0. IDEA 开发工具 ### 运行过程说明 点击进入Main类，启动main方法，根据提示，输入数据文件编号，然后自动运行程序 ### 算法设计 #####分析 0. 实质上是动态规划找最优解问题。 0. 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成），找出01背包问题的最优解以及解组成。 0. 面对每个商品有两种可能性 : 1、包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的 2、还有足够的容量可以装该商品，即当第i件商品能放进去时，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个 2.1 装入商品，价值为：backpackTable[i-1][j-(int)backpackBean.getGoodsWeights().get(i-1)] + (int)backpackBean.getGoodsValues().get(i-1) 2.2 不装入商品，价值为前i-1件上篇价值和：backpackTable[i][j] = backpackTable[i-1][j]; 此时最大价值为上述两种方案中最大的一个 #####算法分析 0. 动态规划填表为O（mn），m为背包大小，n为物品数量 0. 总的时间复杂度为O（mn） #####伪码描述： 1.输入数据文件的编号； 2.while (文件编号 <1 || 文件编号 > 5){ 2.1 重新输入数据文件的编号； 3.通过FileRead.getFileData方法获取数据文件数据（getFileData方法利用FileReader、BufferedReader读取）； 4.将文件数据封装到 BackpackBean 实体bean中； 5.通过背包问题解决类 SolveBackpack.setBackpackTable() 将价值按照动态规划算法放入背包价值表格； 6 通过背包问题解决类 SolveBackpack.findMax() 找出背包问题最优解 #### 0-1背包问题作业代码--整体目录结构 ``` backpack-problem/src/main └─java └─com └─han └─backpack 项目名 ├─bean 实体 └─utils 工具包 └─resource 资源包（包含输入数据文件集） ``` ##### 类设计说明 0. Main ：main方法，程序入口 0. SolveBackpack ： 背包问题解决类 0. BackpackBean ： 背包bean 0. FileRead ： 文件读取类 ##### 数据结构设计 BackpackBean ： 背包bean 0. packageWeight 背包的总容量 0. goodsWeights 每个物品的重量 0. goodsValues 每个物品的价值 0. backpackTable 背包价值表格 ##### 数据文件说明 0. 第一行，背包重量 0. 第二行，每个物品的体积 0. 第三行，每个物品的价值