回溯法

回溯法：对解空间树结点扩展或回溯

确定结点的扩展搜索规则之后，以深度优先方式搜索解空间树，在搜索过程中采用剪枝函数来避免无用搜索。

结点扩展规则：中间结点选择或不选择，叶子结点停止扩展并判断终止条件
深度优先搜索：
剪枝函数：约束函数选择物品总质量不能大于背包可承受重量

解空间树

子集树（此代码是子集树）：达到要求的子集，元素子集。选择某个元素/不选择某个元素
排列树：达到要求的排列，所有元素都在。第1层把那个元素放到第1位，第2层把那个元素放到第2位，依次类推

活结点：还没生孩子的结点
死结点：不能生孩子的结点

剪枝函数

约束函数：剪去不满足约束条件的子树
限界函数：剪去得不到需要解（无解，非最优解）的子树；最大值问题采用上界函数；能求得的上界都不满足要求；即便选择剩下所有物品，也不可能找到一个更好的解

可以找到问题的所有解，当然如果只需要1个解，找到一个解之后结束即可

对比回溯法分枝限界法

回溯法	分枝限界法
回溯法使用栈进行DFS	分枝限界法使用队列进行BFS
回溯法可以找到所有解	分枝限界法只能找到1个解（最优解）
回溯法所有可行结点都会被遍历	分枝限界法不会遍历所有可行结点，每个结点只有1次成为活结点的机会

代码

package xcrj.kchalgorithm.backtracking;

import java.util.Arrays;

/**
 * 问题：
 * 有n个物品 重量分别为{w1，w2，…，wn}，价值分别为{v1，v2，…，vn}
 * 背包能够承受的重量为w
 * 选取一部分物品放入该背包
 * 每个物品要么选中要么不选中
 * 要求选中的物品不仅能够放到背包中，而且具有最大的价值
 * <p>
 * 求解方法：
 * 回溯法
 * - 结点扩展规则：选择或不选择，达到叶子结点之后停止扩展并判断终止条件
 * - 剪枝函数：
 */
public class Knapsack01 {
    /*问题描述*/
    // 总物品数量=解空间树层级（层级从0开始）
    private static int n = 4;
    // 背包能够承受的重量
    private static int availableWeight = 6;
    // 每个物品的重量，下标0不使用，下标代表物品的唯一编号
    private static int[] weights = {0, 5, 3, 2, 1};
    // 每个物品的价值，下标0不使用（根节点），下标代表物品的唯一编号
    private static int[] values = {0, 4, 4, 3, 1};

    /*结果描述*/
    // 最大价值
    private static double maxValue = Double.MIN_VALUE;
    // 最优解 选择哪些物品放进去
    private static int[] opitimalXs = new int[n + 1];

    /**
     * @param i         第i个结点
     * @param sumWeight 0~i-1物品的总质量
     * @param sumValue  0~i-1物品的总价值
     * @param xs        选择的物品
     */
    public static void dfs(int i, int sumWeight, int sumValue, int restWeight, int[] xs) {
        // 叶子结点是一个可能的解，i从1开始，共有4个物品
        if (i > n) {
            // 装得下且价值更大
            if (sumWeight <= availableWeight && sumValue > maxValue) {
                maxValue = sumValue;
                for (int j = 1; j <= n; j++) {
                    // 下标表示物品的唯一编号
                    opitimalXs[j] = xs[j];
                }
            }
        } else {// 中间结点
            // 选择i物品，深度优先
            if (sumWeight + weights[i] <= availableWeight) { // 剪枝函数 约束函数 选择物品总质量不能大于背包可承受重量
                xs[i] = 1;
                dfs(i + 1, sumWeight + weights[i], sumValue + values[i], restWeight - weights[i], xs);
            }
            // 不选择i物品则不更新重量和价值，深度优先
            xs[i] = 0;
            // !! 大于符号原因：选择i物品后的上界重量<可承受重量，即便选择剩下所有物品，也不可能找到一个更好的解；若<走右分枝，下一个右分枝也不选择物品时，仍然满足<条件，会把整个右分支走完
            if (sumWeight + restWeight > availableWeight) { // 限界函数 约束函数 剩余物品价值更大
                dfs(i + 1, sumWeight, sumValue, restWeight - weights[i], xs);
            }
        }
    }

    public static void main(String[] args) {
        int restWeight = 0;
        for (int i = 1; i <= n; i++) {
            restWeight += weights[i];
        }
        dfs(1, 0, 0, restWeight, new int[n + 1]);
        System.out.println("最大价值：" + maxValue);
        System.out.println("装入物品：" + Arrays.toString(opitimalXs));
    }
}