问题描述

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

第 i 种物品：

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

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

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

输出最大价值。

输入格式

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

一、什么是动态规划

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

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

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

二、动态规划的核心思想

一、什么是回溯法

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

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

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

一、双指针（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;
}