dp 背包问题（我自己总结的）
5星 · 超过95%的资源 需积分: 27 20 浏览量
2011-07-30
13:36:46
上传
评论
收藏 215KB PPT 举报 
总结
总结
（下面的方程就按 一种算法理解）
（下面的方程就按 一种算法理解）
昨天我讲的
昨天我讲的
DP
DP
都是直接写出方程了，因为那些的思路相似，相当于套
都是直接写出方程了，因为那些的思路相似，相当于套
用公式，今天主要讲关于
用公式，今天主要讲关于
背包的各种问题的思路
背包的各种问题的思路
。在讲之前，我补充了
。在讲之前，我补充了
本应该是昨天讲的一维和二维最大字段和，还补充了简单
本应该是昨天讲的一维和二维最大字段和，还补充了简单
DP
DP
的路径求
的路径求
法。然后，我举了个数塔的例子。先让你们知道
法。然后，我举了个数塔的例子。先让你们知道
怎么用递推的方法写出
怎么用递推的方法写出
一维数组的方程
一维数组的方程
，在这过程中，我们发现那个
，在这过程中，我们发现那个
循环必须从大到小去写
循环必须从大到小去写
，
，
如果从小到大的话，
如果从小到大的话，
会重复计算一些值（这个性质很重要哦）
会重复计算一些值（这个性质很重要哦）
。然后我
。然后我
们来到
们来到
0/1
0/1
背包问题，写出去一维数组的方程，为了让你们更深一步的
背包问题，写出去一维数组的方程，为了让你们更深一步的
理解这个方程的原理，我举了个例子，画出两张表，表
理解这个方程的原理，我举了个例子，画出两张表，表
1
1
是
是
V——0
V——0
，
，
表
表
2
2
是
是
0———V
0———V
；
；
通过观察，我们发现表
通过观察，我们发现表
2
2
其实就是一个物品可以无
其实就是一个物品可以无
限取的方程的表
限取的方程的表
，也就是说，
，也就是说，
如果方程是
如果方程是
0——V
0——V
，那么这个方程就是
，那么这个方程就是
关于每个物体无限取的问题，
关于每个物体无限取的问题，
即
即
完全背包的
完全背包的
O(VN)
O(VN)
算法。
算法。
然后我有讲了
然后我有讲了
我完全背包的其他算法，主要是
我完全背包的其他算法，主要是
二进制
二进制
0/1
0/1
算法
算法
。接下来是多重背包的
。接下来是多重背包的
不错的算法，分类：
不错的算法，分类：
1
1
。转化成完全背包
。转化成完全背包
O
O
（
（
VN
VN
）算法，
）算法，
2
2
，转化成
，转化成
2
2
进制
进制
0/1
0/1
算法。至于最优算法难度较大，没讲。之后的问题都可以分
算法。至于最优算法难度较大，没讲。之后的问题都可以分
类转化成上面的各类问题，所以我大概提了一下，自己好好理解吧
类转化成上面的各类问题，所以我大概提了一下，自己好好理解吧
……
……
剩余52页未读，继续阅读
资源评论
tester20092012-12-29最近在研究多背包问题，资料对我很有帮助！
honey_fansy2013-03-08谢谢了，不错
