背包问题(0-1背包，完全背包，多重背包知识概念详解)
需积分: 48 187 浏览量
2015-06-14
13:05:32
上传
评论 2
收藏 186KB DOCX 举报
背包问题 (0-1
背包，完全背包，多重背包知识概念详解 )
通过：http://www.cnblogs.com/tanky_woo/archive/
2010/07/31/1789621.html $ $
http://blog.csdn.net/lyhvoyage/article/details/8545852
改编而来
3 种背包的简单概念：
0-1 背包 (ZeroOnePack): 有 N 件物品和一个容量为 V 的背包。每种物品均只有一件
第 i 件物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背
包可使价值总和最大。
完全背包(CompletePack): 有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。
第 i 种物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包
可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包 (MultiplePack): 有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 n[i]件可用，
每件费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些
物品的费用总和不超过背包容量，且价值总和最大。
比较三个题概念，会发现不同点在于每种背包的数量，01 背包是每种只有一件，完全背包是每
种无限件，而多重背包是每种有限件。
—————————————————————————————————————————
—————————————————–
一、0-1 背包：
有 N 件物品和一个容量为 V 的背包。（每种物品均只有一件）第 i 件物品的费用是 c[i]，价值
是 w[i]。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。
则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把这个过程理解下：在前 i 件物品放进容量 v 的背包时，
它有两种情况：
第一种是第 i 件不放进去，这时所得价值为:f[i-1][v]
剩余10页未读，继续阅读
资源评论
