背包问题贪心算法的毕业论文

•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。

贪心与动态规划： 与动态规划不同的是，贪心是 鼠目寸光 ；动态规划是 统揽全局 。

–动态规划：每个阶段产生的都是全局最优解

•第i阶段的“全局”： 问题空间为(a1, … , ai)

•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解

–贪心：每个阶段产生的都是局部最优解

•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai

•第i阶段的“局部最优解”： ai

•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。

–这是贪心算法与动态规划算法的主要区别。

•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

这道题是dp的思想啦，动态规划 (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]= 若k>0且存在1≤i≤n使k-w[i]≥0， ＼ 0 否则。 有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输入背包的负重能力k，返回对应的子背包问题的最优值s[k]：