背包问题是动态规划领域中最经典的组合优化问题之一，核心是在“资源有限”的约束下（如背包容量），选择若干物品以最大化价值（或满足特定条件）。根据物品的选择规则不同，背包问题衍生出多种类型，今天我们就逐一拆解常见的背包问题，并给出清晰的Java实现。

一、背包问题的核心思想

所有背包问题的本质都是 “选择”与“约束”的权衡：

• 约束：背包的容量、重量、体积等有限资源；
• 选择：物品是否选取、选取多少次；
• 目标：最大化价值（或统计方案数、满足特定条件）。

算法简介

模拟退火算法（Simulated Annealing，简称SA）是一种基于物理退火过程的全局优化算法，由Metropolis等人于1953年提出，Kirkpatrick等人在1983年将其应用于组合优化问题。

该算法模拟了金属冶炼中的退火过程：将金属加热到高温，然后缓慢冷却，使原子排列更加有序，最终达到能量最低的稳定状态。在优化问题中，我们用"温度"来控制搜索过程，用"能量"来表示解的质量（能量越低，解越好）。

模拟退火算法的最大特点是：它允许以一定概率接受比当前解更差的解，这使得算法能够跳出局部最优，从而找到全局最优解。

算法简介

禁忌搜索算法（Tabu Search，简称TS）是一种全局优化算法，由Glover教授于1986年提出。该算法模拟了人类的记忆机制，通过记录已经搜索过的解（称为"禁忌"），避免重复搜索，从而跳出局部最优，找到全局最优解。

禁忌搜索算法的核心思想是：在搜索过程中，禁止（禁忌）某些操作或解，以防止算法陷入循环或重复搜索。同时，通过特赦规则（Aspiration Criteria），允许在某些情况下接受禁忌解，以保证算法的全局搜索能力。

与贪心算法不同，禁忌搜索算法允许接受比当前解更差的解，这使得算法能够跳出局部最优，探索更大的搜索空间。

算法简介

粒子群优化算法（Particle Swarm Optimization，简称PSO）是一种基于群体智能的优化算法，由Kennedy和Eberhart于1995年提出。该算法模拟了鸟群或鱼群等生物群体的觅食行为，通过群体中个体之间的信息共享和协作来寻找最优解。

PSO算法的核心思想是：每个个体（称为"粒子"）在搜索空间中移动，它们会记住自己找到的最好位置（个体最优），同时也会知道整个群体中找到的最好位置（全局最优）。每个粒子根据这两个信息来调整自己的速度和位置，逐渐向最优解靠近。

算法原理

基本概念

1. 粒子：代表问题的一个可能解
2. 位置：粒子在搜索空间中的坐标，对应问题的解
3. 速度：粒子移动的方向和快慢
4. 适应度：评价粒子位置好坏的指标
5. 个体最优（pBest）：每个粒子经历过的最好位置
6. 全局最优（gBest）：整个群体中所有粒子经历过的最好位置

在二叉树的算法题中，判断一棵二叉树是否为平衡二叉树是高频考点。这道题不仅考察对平衡二叉树定义的理解，更考验对遍历顺序、时间/空间复杂度优化的深层思考。本文将从暴力解法入手，一步步推导到最优解，带你彻底掌握解题思路。

一、问题定义与核心条件

首先明确平衡二叉树的定义：

一棵空树 或 左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。

拆解核心判断条件：

1. 局部条件：任意节点的左、右子树高度差 ≤ 1；
2. 全局条件：任意节点的左、右子树本身也是平衡二叉树；
3. 边界条件：空树是平衡二叉树。

问题描述

给定 N 种物品 和一个容量为 V 的背包。

第 i 种物品：

• 体积为 vi
• 价值为 wi
• 最多可选 si 件

要求选择若干物品装入背包，使得：

• 物品总体积 ≤ V
• 总价值最大

输出最大价值。

输入格式

N V
v1 w1 s1
v2 w2 s2
...
vN wN sN

一、什么是回溯法

回溯法（Backtracking）是一种 系统地搜索问题所有可能解的算法思想。
它通过 深度优先遍历（DFS） 的方式，不断尝试所有路径，当发现当前路径不满足条件时，立即“回退（backtrack）”到上一步重新选择。

简单来说，回溯法是一种“穷举 + 剪枝”的算法框架，用于解决 组合、排列、子集、路径搜索、数独、八皇后 等问题。

二、回溯与“决策树”的关系

一、什么是动态规划

动态规划（Dynamic Programming，简称 DP）是一种 将复杂问题分解为若干子问题，通过保存子问题的解来避免重复计算 的算法思想。

它常用于 最优解问题（如最短路径、最大收益、最小代价等），核心思想是“状态转移 + 记忆化”。

动态规划适用于 具有重叠子问题 和 最优子结构 的问题。

二、动态规划的核心思想

一、双指针（Two Pointers）

定义

使用两个指针变量在数组或链表中按特定规则同时遍历，常用于解决有序数组、字符串或链表的问题。

使用场景

• 查找有序数组中两个数的和（对撞指针）
• 删除重复元素、快慢指针问题
• 合并有序数组或链表

实现方式（Java）

public boolean twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}