算法分析广义背包实验报告doc - CSDN文库

需积分: 5 20 浏览量更新于2023-04-28 评论收藏 237KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

实验名称___ 广义背包问题实验日期

实验报告要求：1.实验目的 2.实验内容 3. 算法设计 4.程序流程图 5.运行结果 6.实验体会（包括调

试过程中发现的问题及解决方法）。

一、实验目的和要求

广义背包问题的描述：

1. 给定载重量为 M 的背包和 n 种物品，每种物品有一定的重量（w）和价值（v），现在需要设

计算法，在不超过背包载重量 M 的前提下，巧妙选择物品，使得装入背包的物品的总价值最大

化。

2. 广义背包的规则：每种物品均可装入背包多次或不装入（但不能仅装入物品的一部分）。

二、实验内容

先分析 0,1 背包问题的比较方法，再将其动态规划的思想类比的应用到广义背包中去。

首先明确广义背包的抽象模型：背包给定载重为 M，给定 N 种物品具有特定的重量 Wi 和价值

Vi。

根据 0,1 背包的动态规划思想构建广义背包的数学模型。将不同分配方式的背包价值取更大者

MAX 从而得到背包分配的价值最优解。

三、实验步骤

1、算法设计-总体设计

首先将广义背包问题转化为数学描述：

给背包重量 M>0，设有 n 种物品，其重量为 w1，w2......wn。

每种物品对应的价值为 v1，v2......vn。

根据不同的物品分配状态求得对应价值即为。

求装入背包中的最大价值，即求：。

边界限制条件为：

放入物品的重量不得超过背包的容量

其中 x1,x2,x3......xn 是正整数

解决问题的基本思路：

广义背包问题非常类似于 0-1 背包问题，所不同的是每种物品有无限件。也就是从每种物品的角

度考虑，与它相关的策略已并非取或不取两种，而是有取 0 件、取 1 件、取 2 件……等很多种。

如果仍然按照解 01 背包时的思路，令 m（i，j）表示从前 i 种物品选取若干放入一个容量为 j 的

背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程（递归公式）

将背包中价值分为 1.不放第 i 个物品 2.放第 i 个物品两种情况。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余8页未读，立即下载

评论0

/1

粉丝: 107
资源: 37

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈