文档介绍：本文格式为Word版，下载可任意编辑
— 2 —
实验报告动态规划
XXXX
大 学 计 算 机 学 院 实 验 报 告
计算机学院
2022
级
软件工程
本文格式为Word版，下载可任意编辑
— 2 —
实验报告动态规划
XXXX
大 学 计 算 机 学 院 实 验 报 告
计算机学院
2022
级
软件工程
专业
5
班
指导教师
学号
姓名
2022
年 10
月 21
日
劳绩
课程名称 算法分析与设计 测验名称 动态规划 ---0-1 背包问题①理解递归算法的概念
测验目的
②通过模仿 0-1 背包问题，了解算法的思想③练习 0-1 背包问题算法
本文格式为Word版，下载可任意编辑
— 3 —
测验仪器 电脑、 jdk 、 eclipse 和器材
测验：
0-1 背包算法：给定
N 种物品，每种物品都有对应的重量
weight 和价值 value ，一个容
量为 maxWeight 的背包，问：理应如何选择装入背包的物品，使得装入背包的物品的总价值
最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一片面，也 实
验 不能把同一个物品装入屡屡）代码如下所示：
内 public class
KnapsackProblem {
容 /**
、
上 * ***@paramweight 物品重量
机 * ***@paramvalue 物品价值 调 * ***@parammaxweight
背包最大重量
试
程 *
***@return maxvalue[i][j] 中， i 表示的是前 i 个物品数量，
本文格式为Word版，下载可任意编辑
— 3 —
j 表示的是重量
序 */
、 public
static
int knapsack(
int
[]
weight , int
[]
value , int
maxweight ){
程
序
运
行
结
果
实
验
内 int
n = ;
本文格式为Word版，下载可任意编辑
— 4 —
包问题的算法思想：将前 i 个物品放入容量 容 为 w 的背包中的最大价值。有如下两种处境：
、 ①若当前物品的重量小于当前可放入的重量，便可考虑是 上 否要将本件物品放入背包中或者将背包中的某些物品拿出 机 来再将当前物品放进去；放进去前需要对比（不放这个物 调 品的价值）和（这个物品的价值放进去加上当前能放的总 试