实验名称___ 广义背包问题 实验日期
实验报告要求：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 个物品两种情况。
评论0