本文介绍如何通过动态规划解决“在固定预算内购买最多商品种类且总花费最接近预算”的问题，提供完整可运行代码及原理详解。
本文介绍如何通过动态规划解决“在固定预算内购买最多商品种类且总花费最接近预算”的问题，提供完整可运行代码及原理详解。
在购物优化场景中，单纯按价格升序贪心选择（如先买最便宜的商品）虽能最大化商品种类数，但无法保证总花费最接近预算——例如预算为 3000，商品价格为 [500, 800, 1000, 1500]，贪心选前三个得 2300，而选 800+1500=2300 或 500+1000+1500=3000（超预算）不可行；但若存在组合如 500+1000+1500 不可行，而 800+1000+1500=3300 超支，则最优解可能是 500+800+1500=2800 —— 更接近 3000。这本质上是 0/1 背包问题的变种：目标不是最大化价值，而是在容量（预算）约束下，使所选物品总重量（价格）尽可能大（即最接近预算），同时隐含倾向更多物品数量。注意：本题未要求“严格最多种类”，而是“在满足‘尽可能多类型’前提下，总花费最接近预算”。但经典解法中，若所有物品“价值”均设为 1，则等价于“在预算内最多选几件”；而本题更进一步——当存在多种方案种类数相同时，优先选总花费更高的（即更贴近预算）。因此，我们采用以价格为权重、以价格本身为价值的 0/1 背包 DP，确保结果既种类丰富又花费逼近上限。
核心思路：动态规划求解最优子集和
我们构建二维 DP 表 dp[i][j]，表示考虑前 i 个商品、预算上限为 j 时，所能达到的最大总花费（≤ j）。状态转移方程为：
dp[i][j] = max(
dp[i-1][j], # 不选第 i 个商品
dp[i-1][j - price_i] + price_i # 选第 i 个商品（仅当 price_i ≤ j）
)
初始化 dp[0][*] = 0，最终 dp[n][budget] 即为不超过预算的最大可能花费。随后通过逆向回溯还原具体选中的商品名称。
完整可运行代码
def maximize_products(budget, product_list):
if not product_list or budget <blockquote><p>✅ 运行示例输出 ['Banana', 'Apples', 'Oranges']，总价恰好 3000，完美匹配预算，且包含 3 种商品（该预算下最多可选种类数）。</p></blockquote><h3>注意事项与优化建议</h3>
- 时间复杂度：O(n × budget)，适用于预算数值不太大的场景（如 ≤ 10⁴）。若预算极大（如 10⁹），需改用「最小化剩余预算」的 DFS+剪枝或启发式算法。
- 空间优化：DP 表可压缩为一维数组（dp[j]），但回溯时将丢失路径信息；如需复原商品列表，推荐保留二维结构或额外记录决策路径。
- 多解处理：当存在多个组合总花费相同且均为最大值时，当前回溯逻辑返回其中一种（取决于遍历顺序）；如需字典序最小结果，可在回溯时优先尝试不选，或预排序商品。
- 输入鲁棒性：生产环境应增加校验，如过滤负价格、非数字输入、预算非整数等。
该方案不仅解决了“种类最多”，更确保了在同等种类数下总花费最接近预算，是贪心策略的有力升级，适用于电商比价、资源分配、采购计划等实际业务场景。
