实验报告：动态规划01背包问题例文

1、第 PAGE8 页 共 NUMPAGES8 页实验报告：动态规划01背包问题)例文XXXX大 学 计 算 机 学 院 实 验 报 告计算机学院2022级软件工程专业5班指导教师学号姓名2022年 10月 21日成绩课程名称 算法分析p 与设计 实验名称 动态规划 0-1 背包问题理解递归算法的概念实验目的通过模仿 0-1 背包问题，了解算法的思想练习 0-1 背包问题算法实验仪器 电脑、jdk 、eclipse 和器材实验：0-1 背包算法：给定N 种物品，每种物品都有对应的重量weight 和价值 value ，一个容量为 maxWeight 的背包，问：应该如何选择装入背包的物品，使得装入

2、背包的物品的总价值最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也 实验 不能把同一个物品装入多次）代码如下所示：内 public classKnapsackProblem 容 /*、上 * paramweight 物品重量机 * paramvalue 物品价值 调 * parammaxweight背包最大重量试程 *return maxvalueij 中， i 表示的是前 i 个物品数量，j 表示的是重量序 */、publicstaticint knapsack(intweight , intvalue , intmaxweight )程序运行结果 实验内 i

3、ntn = ;包问题的算法思想：将前 i 个物品放入容量 容 为 w 的背包中的最大价值。有如下两种情况：、若当前物品的重量小于当前可放入的重量，便可考虑是 上 否要将本件物品放入背包中或者将背包中的某些物品拿出 机 来再将当前物品放进去；放进去前需要比较（不放这个物 调 品的价值）和（这个物品的价值放进去加上当前能放的总 试 重量减去当前物品重量时取i-1 个物品是的对应重量时候 程 的最高价值），如果超过之前的价值，可以直接放进去，反 序 之不放。、若当前物品的重量大于当前可放入的重量，则不放入 程 背包问题利用动态规划的思路可以这样理解：阶段是“物 序 品的件数”，状态就是“背包剩下的容

4、量” ，fi,v表示设 运 从前 i 件物品中选择放入容量为 V 的背包的最大价值。那 行 么状态转移的方法为:结fiv=maxfi-1v,fi-1v-wi+ci果这个方程可以理解为：只考虑子问题“将前 i 个物品放入容量为 v的背包中的最大价值” 那么可以考虑不放入i，最大价值就和 i无关，就是 fi-1v, 如果放入第i个物品，价值就是 fi-1v-wi+valuei, 只取最大值即可。实验内容、上机调试程序、程序运行结果 就是喜欢这种写法。import java.util.Scanner; public cla Main public static void main(String ar

5、gs)Scanner sc = new Scanner(System.in);int Num = sc.nextInt;/物品的个数（编号从0开始），不超过100int Col = sc.nextInt;/背包容量，不超过1000int d = new intCol+1;/表示前i个（会不断更新）物品装到剩余容量为j的背包中的最大重量,当然不包括编号为i的物品int Ver = 0;int Weight = 0; while(sc.hasNext) for(int i=0; i/不需要用数组存储体积和价值了，边读入边处理数据即可if(i 0)Ver = sc.nextInt;Weight = sc.nextInt; for(int j=Col; j=0; j-)if(i0 & j=Ver) dj =