01背包np_背包问题的动态规划_背包的动态规划问题(2)

背包问题测试:

package com.wootion.algorithmic;

public class KnapsackTest {  
    
    public static void main(String[] args) {  
          
        Knapsack[] bags = new Knapsack[] {  
                new Knapsack(2,13), new Knapsack(1,10),  
                new Knapsack(3,24), new Knapsack(2,15),  
                new Knapsack(4,28), new Knapsack(5,33),  
                new Knapsack(3,20), new Knapsack(1, 8)  
        };  
        
        int totalWeight = 10;  
        KnapsackProblem kp = new KnapsackProblem(bags, totalWeight);  
          
        kp.solve();  
        System.out.println(" -------- 该背包问题实例的解: --------- ");  
        System.out.println("最优值：" + kp.getBestValue());   
        System.out.println("最优解【选取的背包】: ");  
        System.out.println(kp.getBestSolution());  
        System.out.println("最优决策矩阵表：");  
        int[][] bestValues = kp.getBestValues();  
        for (int i=0; i < bestValues.length; i++) {  
            for (int j=0; j < bestValues[i].length; j++) {  
                System.out.printf("%-5d", bestValues[i][j]);  
            }  
            System.out.println();  
        }  
    }  
}   

动态规划法总结：

1. 动态规划法用于求解非最优化问题：

当问题实例P(n)的解由子问题实例的解构成时，比如 P(n) = P(n-1) + P(n-2) [斐波那契数列] ，而 P(n-1) 和 P(n-2)可能包含重合的子问题，可以使用动态规划法，通过自底向上的迭代，求解较小子问题实例的解，并作为求解较大子问题实例的解的基础。背包问题的动态规划关键思想 是： 避免对子问题重复求解。

比如： 求斐波那契数 F(5)：

F(5) = F(4) + F(3);

子问题： F(4) = F(3) + F(2) ;

F(3) = F(2) + F(1);

F(2) = F(1) + F(0)

F(2) = F(1) + F(0);

子问题： F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

由上面的计算过程可知，如果单纯使用递归式，则子问题 F(2) 被重复计算了2次；当问题实例较大时，这些重复的子问题求解就会耗费大量不必要的时间。若使用动态规划法，将 F(2) 的值存储起来，当后续计算需要的时候，直接取出来， 就可以节省不少时间。

另一个比较典型的例子是： 求解二项式系数 C(n, k) = C(n-1, k) + C(n-1, k-1)

2. 动态规划法求解最优化问题：

当问题实例P(n) 的最优解可以从 问题实例 P(n-1) 的最优解 构造出来时，可以采用动态规划法，一步步地构造最优解。

关键是掌握动态规划法求解问题时的分析方法，如何从问题导出解的递推式。实际上，当导出背包问题的递归式后，后来的工作就简单多了，如何分析背包问题，导出其最优解的递推式，我觉得，这才是最关键的地方！问题分析很重要！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-30102-2.html