动 态 规 划(Dynamic programming)背包问题资源分配问题生产计划问题复合系统工作可靠性问题有一个徒步旅行者，其可携带物品重量的限度为 a 公斤，设有 n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品 1 2 j n重量（公斤 /件） a1 a2 aj an每件使用价值 c1 c2 cj cn这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。背包问题设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下：用动态规划方法求解，令fk(y) = 总重量不超过 y 公斤，包中只装有前 k 种物品时的最大使用价值。其中 y 0， k 1,2, , n 。 所以问题就是求 fn(a) 其递推关系式为：当 k=1 时，有：例题：求下面背包问题的最优解物品 1 2 3重量（公斤） 3 2 5使用价值 8 5 12解： a 5 ，问题是求 f3(5)所以，最优解为 X（ 1 . 1 . 0）， 最优值为 Z = 13。
