背包动态规划

背包动态规划（backpack dynamic planning），工学-控制科学与工程-智能系统-智能系统-规划-序列规划，给定一组物品，每种物品都有自己的体积和价值价格，求解在背包体积一定的条件下，如何选择，才能使得背包内物品的总价值最高的规划方法，是动态规划的一个分支。20世纪50年代初美国数学家R.E.贝尔曼（Richard Ernest Bellman，1920～1984）等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段决策过程的优化问题转化为一系列单阶段决策过程的优化问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年贝尔曼出版了专著《动态规划》（Dynamic Programming），这是该领域的第一本著作。动态规划一般可分为线性动态规划，区域动态规划，树形动态规划和背包动态规划。背包动态规划可分为：0-1背包动态规划、完全背包动态规划、多重背包动态规划和混合背包动态规划。（1）0-1背包动态规划。