文档介绍：XXXX 大 学 计 算 机 学 院 实 验 报 告
计算机学院 2017 级软件工程专业—班 指导教师
学号 姓名 2019年10月_21_日 成绩
课程名称
算法分析与设计
实验名称
动态规划---0-1背包问题
XXXX 大 学 计 算 机 学 院 实 验 报 告
计算机学院 2017 级软件工程专业—班 指导教师
学号 姓名 2019年10月_21_日 成绩
课程名称
算法分析与设计
实验名称
动态规划---0-1背包问题
实验目的
理解递归算法的概念
通过模仿0-1背包问题，了解算法的思想
练****0-1背包问题算法
实验仪器
和器材
电脑、jdk、eclipse
实 验 内 容
、
上 机 调 试 程 序
、
程 序 运 行 结 果
实验：0T背包算法：给定N种物品，每种物品都有对应的重量weight和价值value, —个容 量为maxWeight的背包，问：应该如何选择装入背包的物品，使得装入背包的物品的总价值 最大。(面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也 不能把同一个物品装入多次)代码如下所示：
public class KnapsackProblem {
/**
***@param weight 物品重量
***@param value 物品价值
***@param maxweight背包最大重量
* ***@return maxvalue[i][j]中，i表示的是前i个物品数量，j表示的是重量
*/
public static int knapsack(int [] weight, int [] value, int maxweight){ int n = weight. length;//物品件数
//最大价值数组为maxvalie[N+l][maxweight+l];因为数组的下标是从0开始的； maxva1ue[N+l][maxweight+l]第一个数字表示的是前n+1个背包，第二个数组表示的是前n+1 个背包的重量
int [] [] maxvalue = new int[n+1][maxweight + 1];
//物品件数和物品重量为0时，价值也为0
for (int i =0; i<maxweight; i++){
maxvalue [0][i]=0;
}
for (int i = 0; i<n+1; i++){
maxvalue [i][0]=0;
}
//i:表示只能拿前i件物品(数组的下标是从0开始的，所以对应到weight和value 里面都是i-1的位置)
//j:表示假设能取的总重量为j
//n:表示的是物品件数
实 验 内 容
上 机 调 试 程 序
程 序 运 行 结 果
System. ("选中的物品是第”)；
for (int i=l;i〈=n;i++){
for (int j=l;j〈=maxweight;j++){
//当前最大价值等于放前一件的最大价值
maxvalue [i][j] = maxvalue[i-l][j];
//如果当前物品的重量小于总重量，可以放进去或者拿出别的东西再 放进去
if (weight[i-1] <