基本信息

---

下载

文档摘要

---

PAGE1

PAGE1

动态规划与贪心算法的比较：分数背包问题

1动态规划简介

1.1动态规划的基本概念

动态规划（DynamicProgramming，简称DP）是一种在计算机科学和数学中用于解决最优化问题的算法策略。它将问题分解为更小的、相互重叠的子问题，并存储子问题的解，避免重复计算，从而达到提高效率的目的。动态规划的核心在于“状态转移方程”，即如何从已知的子问题解推导出更大问题的解。

1.1.1例子：斐波那契数列

斐波那契数列是一个经典的动态规划问题。数列定义为：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n=2)