利用动态规划解决01背包问题01背包问题动态规划.docx
版权申诉
198 浏览量
2023-03-09
18:47:58
上传
评论
收藏 54KB DOCX 举报
利用动态规划解决 01 背包问题 01 背包问题动态规
划
背包问题是一个经典的动态规划模型 ,很多关于算法的教材都把
它作为一道例题,该问题既简单又容易理解,而且在某种程度上还能够
揭示动态规划的本质。
将具有不同重量和价值的物体装入一个有固定载重量的背包 ,以
获取最大价值,这类问题被称为背包问题。
背包问题可以扩展出很多种问题,而 01 背包问题是最常见、最有
代表性的背包问题。
一、问题描述
给定一个载重量为 M 的背包及 n 个物体,物体 i 的重量为 wi、价
值为 pi,1≤i≤n,要求把这些物体装入背包 ,使背包内的物体价值总量
最大。此处我们讨论的物体是不可分割的 ,通常称这种物体不可分割
的背包问题为 01 背包问题。
二、基本思路
01 背包问题的特点是:每种物体只有一件,可以选择放或者不放。
假设:xi 表示物体 i 被装入背包的情况,xi=0,1。当 xi=0 时,表示物体没
有被装入背包;当 xi=1 时,表示物体被装入背包。根据问题的要求,有如
下的约束方程(1)和目标函数(2):
三、利用动态规划法求解 01 背包问题
(一)动态规划算法的基本思想
动态规划算法通常用于求解具有某种最优性质的问题。在这类问
题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到
具有最优值的解。动态规划算法与分治法类似 ,其基本思想也是将待
求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解
得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,
资源评论
G11176593
- 粉丝: 6643
- 资源: 3万+
