实验报告：动态规划---0-1背包问题)

XXXX大 学 计 算 机 学 院 实 验 报 告

计算机学院 2017 级 软件工程 专业 5 班 指导教师 学号 姓名 2019年 10 月 21 日 成绩 课程名称 算法分析与设计 实验名称 动态规划---0-1背包问题 ①理解递归算法的概念 实验目的 ②通过模仿0-1背包问题，了解算法的思想 ③练习0-1背包问题算法 实验仪器 和器材 实 验 内 容 、 上 机 调 试 程 序 、 程 序 运 行 结 果 * @return maxvalue[i][j]中，i表示的是前i个物品数量，j表示的是重量 */ public static int knapsack(int [] weight,int [] value,int maxweight){ /** * @param weight 物品重量 * @param value 物品价值 * @param maxweight 背包最大重量 最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也不能把同一个物品装入多次）代码如下所示： public class KnapsackProblem { 电脑、jdk、eclipse 实验：0-1背包算法：给定N种物品，每种物品都有对应的重量weight和价值value，一个容量为maxWeight的背包，问：应该如何选择装入背包的物品，使得装入背包的物品的总价值 实 验 内 容 、 上 机 调 试 程 序 、 程 序 运 行 结 果 i个物品放入容量为w的背包中的最大价值。有如下两种情况： ①若当前物品的重量小于当前可放入的重量，便可考虑是否要将本件物品放入背包中或者将背包中的某些物品拿出来再将当前物品放进去；放进去前需要比较（不放这个物品的价值）和（这个物品的价值放进去加上当前能放的总重量减去当前物品重量时取i-1个物品是的对应重量时候的最高价值），如果超过之前的价值，可以直接放进去，反之不放。 ②若当前物品的重量大于当前可放入的重量，则不放入 背包问题利用动态规划的思路可以这样理解：阶段是“物品的件数”，状态就是“背包剩下的容量”，f[i,v]表示设从前i件物品中选择放入容量为V的背包的最大价值。那么状态转移的方法为: f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]} 这个方程可以理解为：只考虑子问题“将前i个物品放入容量为v的背包中的最大价值”那么可以考虑不放入i，最大价值就和i无关，就是f[i-1][v],如果放入第i个物品，价值就是f[i-1][v-w[i]]+value[i],只取最大值即可。 int n = ;包问题的算法思想： 将前 实 验 内 容 、 上 机 调 试 程 序 、 程 序 运 行 结 果