最优（Optimal，OPT）算法

最优（Optimal，OPT）算法通常指的是在给定条件下找到最佳解决方案的策略或方法，它通常与动态规划（Dynamic Programming, DP）相关，因为动态规划常常用于解决这类问题。动态规划通过分解大问题为小问题并保存子问题的解来达到优化目的。

一个经典的动态规划问题如背包问题[^4]，其最优解算法可以描述如下：

1. **定义状态**: 通常定义一个二维数组 `dp[i][j]`，表示前 `i` 个物品，容量为 `j` 的背包能获得的最大价值。

2. **初始化**: 对于每个物品 `i` 和容量 `0`，`dp[i]` 初始值为 0，因为不携带任何物品的价值为 0。

3. **填充状态**: 从第一个物品开始，对于每个物品，考虑两种选择：不放入背包（`dp[i-1][j]`）或放入背包（`value[i] + dp[i-1][j-weight[i]]`），取其中价值更大的作为当前状态的值。

4. **计算最优解**: 最终的最优解在 `dp[n][W]`，其中 `n` 是物品数量，`W` 是背包容量。

**Python 示例** (假设有一个物品价值和重量列表 `values` 和 `weights`):

def knapsack_optimal(values, weights, capacity):
    dp = [ * (capacity + 1) for _ in range(len(values) + 1)]
    
    for i in range(1, len(values) + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]

    return dp[-1][-1]

# 使用示例
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50
optimal_value = knapsack_optimal(values, weights, capacity)