一、01背包问题

给定：

• 价值数组 v = {8, 10, 6, 3, 7, 2}
• 重量数组 w = {4, 6, 2, 2, 5, 1}
• 背包容量 c = 12

解决方案分析

1. 二维动态规划

定义 m[i,j]：从前 i 个物品中选择，总体积不超过 j 的最大价值。

• 如果 j < w[i-1]：m[i,j] = m[i-1,j]（不能选择第 i 个物品）
• 否则：m[i,j] = max(m[i-1,j], m[i-1,j-w[i-1]] + v[i-1])（选择或不选择第 i 个物品）

系列文章

【基础算法】1.排序及二分

【基础算法】2.高精度&前缀和与差分