Java实现动态规划法求解0/1背包问题

摘要：使用动态规划法求解0/1背包问题。

难度：初级

0/1背包问题的动态规划法求解，前人之述备矣，这里所做的工作，不过是自己根据理解实现了一遍，主要目的还是锻炼思维和编程能力，同时，也是为了增进对动态规划法机制的理解和掌握。

值得提及的一个问题是，在用 JAVA 实现时，是按算法模型建模，还是用对象模型建模呢？如果用算法模型，那么背包的值、重量就直接存入二个数组里；如果用对象模型，则要对背包以及背包问题进行对象建模。思来想去，还是采用了对象模型，尽管心里感觉算法模型似乎更好一些。有时确实就是这样，对象模型虽然现在很主流，但也不是万能的，采用其它的模型和视角，或许可以得到更好的解法。

背包建模：

package algorithm.dynamicplan;
public class Knapsack {
    
    /** 背包重量  */
    private int weight;
    
    /** 背包物品价值  */
    private int value;
    /***
     * 构造器
     */
    public Knapsack(int weight, int value) {
        this.value = value;
        this.weight = weight;
    }
    public int getWeight() {
        return weight;
    }
    
    public int getValue() {
        return value;
    }
    
    public String toString() {
        return "[weight: " + weight + " " + "value: " + value + "]";  
    }
}

　　背包问题求解：

/**
 * 求解背包问题：
 * 给定 n 个背包，其重量分别为 w1,w2,……,wn, 价值分别为 v1,v2,……,vn
 * 要放入总承重为 totalWeight 的箱子中， 
 * 求可放入箱子的背包价值总和的最大值。
 * 
 * NOTE: 使用动态规划法求解 背包问题
 * 设 前 n 个背包，总承重为 j 的最优值为 v[n,j], 最优解背包组成为 b[n];
 * 求解最优值：
 * 1. 若 j < wn, 则 ： v[n,j] = v[n-1,j];
 * 2. 若  j >= wn, 则：v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。
 * 
 * 求解最优背包组成：
 * 1. 若 v[n,j] > v[n-1,j] 则 背包 n 被选择放入 b[n], 
 * 2. 接着求解前 n-1 个背包放入 j-wn 的总承重中， 
 *    于是应当判断 v[n-1, j-wn] VS v[n-2,j-wn], 决定 背包 n-1 是否被选择。
 * 3. 依次逆推，直至总承重为零。
 *    
 *    重点： 掌握使用动态规划法求解问题的分析方法和实现思想。
 *    分析方法： 问题实例 P(n) 的最优解S(n) 蕴含 问题实例 P(n-1) 的最优解S(n-1);
 *              在S(n-1)的基础上构造 S(n) 
 *    实现思想： 自底向上的迭代求解 和 基于记忆功能的自顶向下递归
 */
package algorithm.dynamicplan;
import java.util.ArrayList;
public class KnapsackProblem {
    
    /** 指定背包 */
    private Knapsack[] bags;
    
    /** 总承重  */
    private int totalWeight;
    
    /** 给定背包数量  */
    private int n;
    
    /** 前 n 个背包，总承重为 totalWeight 的最优值矩阵  */
    private int[][] bestValues;
    
    /** 前 n 个背包，总承重为 totalWeight 的最优值 */
    private int bestValue;
    
    /** 前 n 个背包，总承重为 totalWeight 的最优解的物品组成 */
    private ArrayList<Knapsack> bestSolution;
    
    public KnapsackProblem(Knapsack[] bags, int totalWeight) {
        this.bags = bags;
        this.totalWeight = totalWeight;
        this.n = bags.length;
        if (bestValues == null) {
            bestValues = new int[n+1][totalWeight+1];
        }
    }
    
    /**
     * 求解前 n 个背包、给定总承重为 totalWeight 下的背包问题
     * 
     */
    public void solve() {
        
        System.out.println("给定背包：");
        for(Knapsack b: bags) {
            System.out.println(b);
        }
        System.out.println("给定总承重: " + totalWeight);
        
        // 求解最优值
        for (int j = 0; j <= totalWeight; j++) {
            for (int i = 0; i <= n; i++) {
            
                if (i == 0 || j == 0) {
                    bestValues[i][j] = 0;
                }    
                else 
                {
                    // 如果第 i 个背包重量大于总承重，则最优解存在于前 i-1 个背包中，
                    // 注意：第 i 个背包是 bags[i-1]
                    if (j < bags[i-1].getWeight()) {
                        bestValues[i][j] = bestValues[i-1][j];
                    }    
                    else 
                    {
                        // 如果第 i 个背包不大于总承重，则最优解要么是包含第 i 个背包的最优解，
                        // 要么是不包含第 i 个背包的最优解， 取两者最大值，这里采用了分类讨论法
                        // 第 i 个背包的重量 iweight 和价值 ivalue
                        int iweight = bags[i-1].getWeight();
                        int ivalue = bags[i-1].getValue();
                        bestValues[i][j] = 
                            Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);        
                    } // else
                } //else         
           } //for
        } //for
        
        // 求解背包组成
        if (bestSolution == null) {
            bestSolution = new ArrayList<Knapsack>();
        }
        int tempWeight = totalWeight;
        for (int i=n; i >= 1; i--) {
           if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {
               bestSolution.add(bags[i-1]);  // bags[i-1] 表示第 i 个背包
               tempWeight -= bags[i-1].getWeight();
           }
           if (tempWeight == 0) { break; }
        }
        bestValue = bestValues[n][totalWeight];
       }
    
    /**
     * 获得前  n 个背包， 总承重为 totalWeight 的背包问题的最优解值
     * 调用条件： 必须先调用 solve 方法
     * 
     */
    public int getBestValue() {    
        return bestValue;
    }
    
    /**
     * 获得前  n 个背包， 总承重为 totalWeight 的背包问题的最优解值矩阵
     * 调用条件： 必须先调用 solve 方法
     * 
     */
    public int[][] getBestValues() {
        
        return bestValues;
    }
    
    /**
     * 获得前  n 个背包， 总承重为 totalWeight 的背包问题的最优解值矩阵
     * 调用条件： 必须先调用 solve 方法
     * 
     */
    public ArrayList<Knapsack> getBestSolution() {
        return bestSolution;
    }
    
}

　　背包问题测试：

package algorithm.dynamicplan;

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 = 12;
        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) 的最优解构造出来时，可以采用动态规划法，一步步地构造最优解。

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