内容发布更新时间 : 2024/12/29 13:36:42星期一 下面是文章的全部内容请认真阅读。
算法设计与分析课内实验报告
题 目: 动态规划问题
专业名称: 班 级 : 学生姓名:
学号(8位): 指导教师: 设计时间:
一. 设计目的
掌握动态规划问题的解决方案。
二. 设计内容
(一)给定n个物品和一个容量为C的背包,物品i的重量为wi,其价值为vi,背
包问题是如何选择装入背包的物品,使得装入背包中物品的总价值最大。注意和0/1背包的区别,在背包问题中,可以将某种物品的一部分装入背包中,但不可以重复装入。
1.算法设计思想
先考虑这个物品放入的时候可以获得的最大价值(这个物品的价值+剩余背包(背包总容量-该物品重量)容量可以获得的最大价值),再考虑不放入这个物品的时候可以获得的最大价值(剩余背包容量(此时就是背包总重量)可以获得的最大价值),然后将2者进行比较,那种结果的价值大就将哪种结果的价值保存下来,依次类推。
2.主要模块流程图。
开始
初始化,输入物品重量:c[] 物品价值:v[] C:背包容量 W.length==0 继续判断 不成立;表示还可以继续装
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; }
//填充其他行和列