本文介绍一种基于动态规划的精确解法，用于在给定预算下选择尽可能多种类的商品，且总花费最接近但不超过预算——本质是0/1背包问题的变种，目标不是最大化价值，而是最大化物品数量（品类数），其次才是填满预算。
本文介绍一种基于动态规划的精确解法，用于在给定预算下选择尽可能多种类的商品，且总花费最接近但不超过预算——本质是0/1背包问题的变种，目标不是最大化价值，而是最大化物品数量（品类数），其次才是填满预算。
在实际购物或资源分配场景中，仅按价格升序贪心选取（如先买最便宜的）虽能快速获得较多品类，但无法保证总花费最接近预算。例如：预算3000元，商品为 [("Apples", 1000), ("Banana", 500), ("Oranges", 1500), ("Grapes", 2000), ("Cherry", 800)]，贪心法会选 Banana(500) → Apples(1000) → Oranges(1500)，累计3000元，看似完美；但若将 Oranges 替换为 Cherry(800)，则可选 Banana+Apples+Cherry=2300元（3种），而遗漏了更优的 Banana+Oranges=2000元（2种）？不——关键在于：“最多品类”是首要目标，“最接近预算”是次要目标（在品类数相同前提下）。
因此，标准0/1背包需稍作改造：状态定义改为 dp[i][j] = 使用前 i 个商品、预算 j 时能购买的最大品类数；若品类数相同，则优先记录更高总花费（即更接近预算）。以下是优化后的完整实现：
def maximize_products(budget, product_list):
n = len(product_list)
# dp[i][j] 表示前 i 个商品、预算 j 下能买到的最大品类数
# cost[i][j] 表示对应最大品类数时的实际总花费（用于后续回溯选最接近预算的方案）
dp = [[0] * (budget + 1) for _ in range(n + 1)]
cost = [[0] * (budget + 1) for _ in range(n + 1)]
# 填充 DP 表
for i in range(1, n + 1):
name, price = product_list[i - 1]
for j in range(budget + 1):
# 不选第 i 个商品
dp[i][j] = dp[i-1][j]
cost[i][j] = cost[i-1][j]
# 选第 i 个商品（前提是价格不超当前预算）
if price dp[i][j]) or \
(new_count == dp[i][j] and new_cost > cost[i][j]):
dp[i][j] = new_count
cost[i][j] = new_cost
# 回溯构造结果：从 dp[n][budget] 开始，找具体选了哪些商品
selected = []
j = budget
for i in range(n, 0, -1):
# 如果当前状态由选择第 i 个商品转移而来
name, price = product_list[i-1]
if price <p>✅ <strong>关键改进点说明：</strong> </p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/ai/1452" title="Prisma"><img
src="https://img.php.cn/upload/ai_manual/001/431/639/68b6ccae3f219838.png" alt="Prisma" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/ai/1452" title="Prisma" class="overflowclass">Prisma</a>
<p class="overflowclass">Prisma是一款通过 AI 风格迁移把照片转换为艺术画作的移动修图应用。</p>
</div>
<a rel="nofollow" href="/ai/1452" title="Prisma" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
- 使用双DP表：dp[][] 记录最大品类数，cost[][] 同步记录该品类数下的最高可行花费；
- 状态转移时，不仅比较品类数，当品类数相等时，优先保留花费更高的方案（即更贴近预算）；
- 回溯过程严格依据 dp 和 cost 的联合决策，确保结果既满足“最多品类”，又在同类解中“最接近预算”。
⚠️ 注意事项：
- 时间复杂度为 O(n × budget)，适用于预算数值不太大的场景（如万元以内）；若预算过大（如百万级），需考虑空间优化（滚动数组）或启发式近似算法；
- 所有价格必须为非负整数，且 budget 为整数；若含小数，建议统一放大为整数（如乘100处理分币）；
- 本解法默认每种商品至多购买1件（0/1约束），符合“最多类型”的原始需求；若允许多件同类型，问题将变为完全背包，需另行设计。
通过该动态规划方案，你不仅能获得品类数量最多的组合，还能在所有同等品类数的方案中，自动选出总花费最接近预算的最优解——真正实现“买得多样，花得精准”。
