动态规划法：背包问题

动态规划法：背包问题2015-02-17一几个概念：

最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不止一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值的可行解成为最优解，这类问题称为最优化问题。

二最优性原理：

对于一个具有n个输入的最优化问题，其求解的过程往往可以划分为若干个阶段，每一个阶段的决策仅依赖前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一个阶段的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。

在每一个阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。

多阶段决策过程满足最优性原理：无论决策过程的初始状态和初始决策是什么，其余决策必须相对于初始决策所产生的当前状态，构成一个最优决策序列。

如果一个问题满足最优性原理通常称此问题具有最优子结构性质。

三特征

我们知道动态规划是求解全局最优解的有效方法，一般来说能用动态规划算法求解的问题具有以下两个显著特称：

具有最优子结构性质，也就是说可以递归的定义最优解。

能够分解为相互重叠的若干自问题。

最优解中也包含其子问题的最优解。

四设计方案

动态规划法设计方案

分段：将原问题分解为若干个相互重叠的子问题；

分析：分析问题是否满足最优子结构性质，找出动态规划函数递推式；

求解：利用递推式自底向上计算，实现动态规划过程。

五 01背包问题

0/1背包问题中，物品i或者被放入背包，或者不被放入背包，设Xi表示物品i装入背包的情况，则当Xi=0时，表示物品i没有被装入背包，Xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：

图 1 约束条件

图2 目标函数

01背包的状态转换方程f[i,j]= Max{ f[i-1,j-Wi]+Pi（ j >= Wi ）, f[i-1,j] }

f[i,j]表示在前i件物品中选择若干件放在承重为j的背包中，可以取得的最大价值。

Pi表示第i件物品的价值。

决策：为了背包中物品总价值最大化，第i件物品应该放入背包中吗？

六动态规划法解决方案

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和

表10/1背包问题动态规划法