内容发布更新时间 : 2024/11/10 16:26:27星期一 下面是文章的全部内容请认真阅读。
算法设计与分析课内实验报告
题 目： 动态规划问题
专业名称： 班 级 ： 学生姓名：
学号（8位）： 指导教师： 设计时间：
一. 设计目的
掌握动态规划问题的解决方案。
二. 设计内容
（一）给定n个物品和一个容量为C的背包，物品i的重量为wi,其价值为vi，背
包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大。注意和0/1背包的区别，在背包问题中，可以将某种物品的一部分装入背包中，但不可以重复装入。
1．算法设计思想
先考虑这个物品放入的时候可以获得的最大价值（这个物品的价值+剩余背包(背包总容量-该物品重量)容量可以获得的最大价值），再考虑不放入这个物品的时候可以获得的最大价值（剩余背包容量(此时就是背包总重量)可以获得的最大价值），然后将2者进行比较，那种结果的价值大就将哪种结果的价值保存下来，依次类推。
2．主要模块流程图。
开始
初始化，输入物品重量：c[] 物品价值：v[] Ｃ:背包容量 W.length＝＝０ 继续判断 不成立;表示还可以继续装
3．重点设计及编码
public class tow {
public static int knapSack(int[] w, int[] v, int C) { int size = w.length; if (size == 0) { return 0; }
int[][] dp = new int[size][C + 1]; //初始化第一行
//仅考虑容量为C的背包放第0个物品的情况 for (int i = 0; i <= C; i++) {
dp[0][i] = w[0] <= i ? v[0] : 0; }
//填充其他行和列