背包问题动态规划.doc

动态规划 动态规划的逆向思维法动态规划是一种思维方法，没有统一的、具体的模式。动态规划可以从多方面去考察，不同的方面对动态规划有不同的表述。我们不打算强加一种统一的表述，而是从多个角度对动态规划的思维方法进行讨论，希望大家在思维具体问题时，也能够从多个角度展开，这样收获会更大。??? 逆向思维法是指从问题目标状态出发倒推回初始状态或边界状态的思维方法。如果原问题可以分解成几个本质相同、规模较小的问题，很自然就会联想到从逆向思维的角度寻求问题的解决。??? 你也许会想，这种将大问题分解成小问题的思维不就是分治法吗?动态规划是不是分而治之呢?其实，虽然我们在运用动态规划的逆向思维法和分治法分析问题时，都使用了这种将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解出来的各个子问题的性质不同。??? 分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。??? 动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效的一个原因。??? 动态规划的逆向思维法的要点可归纳为以下三个步骤：??? (1)分析最优值的结构，刻画其结构特征；??? (2)递归地定义最优值；??? (3)按自底向上或自顶向下记忆化的方式计算最优值。??? 【例题5】背包问题描述：??? 有一个负重能力为m的背包和n种物品，第i种物品的价值为v[i]，重量为w[i]。在不超过背包负重能力的前提下选择若干个物品装入背包，使这些的物品的价值之和最大。每种物品可以不选，也可以选择多个。假设每种物品都有足够的数量。??? 分析：??? 从算法的角度看，解决背包问题一种最简单的方法是枚举所有可能的物品的组合方案并计算这个组合方案的价值之和，从中找出价值之和最大的方案。显然，这种靠穷举所有可能方案的方法不是一种有效的算法。??? 但是这个问题可以使用动态规划加以解决。下面我们用动态规划的逆向思维法来分析这个问题。??? (1)背包问题最优值的结构??? 动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动态规划的显著特征。??? 对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力为 m-w[i] 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包问题具有最优子结构。??? (2)递归地定义最优值??? 动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问题而言，有状态转移方程：???????? ／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)??? s[k]=??????? 若k0且存在1≤i≤n使k-w[i]≥0，???????? ＼ 0??? 否则。??? 有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输入背包的负重能力k，返回对应的子背包问题的最优值s[k]： ? function knapsack(k:integer):integer；? begin??? knapsack:=0；??? for? i:=1? to n do????? if k-w[i]=0 then????? begin??????? t:=knapsack(k-w[i])+v[i]；??????? if knapsack t then knapsack:=t；????? end;? end；??? 上述递归算法在求解过程中反复出现了一个子问题，且对每次重复出现的子问题都要重新解一次，这需要多花费不少时间。下面先考虑一个具体的背包问题。例如，当??? m=3，n=2，v[1]=1，w[1]=1，v[2]=2，w[2]=2，??? 图1示出了由调用knapsack(3)所产生的递归树，每一个结点上标有参数k的值，请注意某些数出现了多次。???????? 3??????? ／＼?????? 2??? 1???? ／＼??? ＼??? 1??? 0??? 0? ／