01背包问题用各种算法实现

01背包问题是动态规划（Dynamic Programming，简称DP）中的一个经典问题，它涉及一个有限的物品集合，每个物品有一个价值（valuation）和一个重量（weight），目标是在不超过给定总重量的情况下，选择物品以最大化总价值。以下是几种常见的算法实现：

1. **贪心算法**：不是所有情况都能找到最优解，例如当存在物品之间的价值密度差异很大时，可能会错失一些组合。但对于特定场景，如物品只有一种价值密度时，可以采用贪心策略。

2. **暴力穷举法**：对每种可能的组合都检查，时间复杂度较高，不适合大规模数据。

3. **动态规划**：
- **表格填充法**（表征法）：创建一个二维数组，记录每个可能重量下包含某物品的最大价值，通过遍历所有状态得到结果。
- **递推式**：通常定义两个状态`dp[i][w]`表示前i个物品总重量不超过w时的最大价值。从最小重量到最大重量逐次计算。

4. **回溯法**：一种用于解决组合优化问题的通用算法，在背包问题中，如果当前装入物品超出了容量，就回溯尝试其他物品。

5. **分支限界法**：结合了搜索树和剪枝技术，适用于物品价值与体积比值变化大的情况。