实验报告：动态规划---0-1背包问题)范文
XXXX
大 学 计 算 机 学 院 实 验 报 告
计算机学院
2017
级
软件工程
专业
5
班
指导教师
学号
姓名
2019
年 10
月 21
日
成绩
课程名称 算法分析与设计 实验名称 动态规划 ---0-1 背包问题①理解递归算法的概念
实验目的
②通过模仿 0-1 背包问题，了解算法的思想③练习 0-1 背包问题算法
实验仪器 电脑、 jdk 、 eclipse 和器材
实验：
0-1 背包算法：给定
N 种物品，每种物品都有对应的重量
weight 和价值 value ，一个容
量为 maxWeight 的背包，问：应该如何选择装入背包的物品，使得装入背包的物品的总价值
最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也 实
验 不能把同一个物品装入多次）代码如下所示：
内 public class
KnapsackProblem {
容 /**
、
上 * @paramweight 物品重量
机 * @paramvalue 物品价值 调 * @parammaxweight
背包最大重量
试
程 *
@return maxvalue[i][j] 中， i 表示的是前 i 个物品数量，
j 表示的是重量
序 */
、 public
static
int knapsack(
int
[]
weight , int
[]
value , int
maxweight ){
程
序
运
行
结
果
实
验
内 int
n = ;
包问题的算法思想：将前 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], 只取最大值即可。
实
验
内
容
、
上
机
调
试
程
序
、
程
序
运
行
结
果
下一篇：果蝇三点测交实验报告