动态规划：求解指定重量橙子采购最小成本的思路问询

问题描述 #

给定正整数数组cost，其中cost[i]代表填充i + 1公斤橙子的成本（采用0索引）。假设每种i + 1公斤的橙子供应无限，我们需要计算采购恰好w公斤橙子的最小成本。

一、暴力递归解法详解 #

你写的暴力递归代码核心是枚举所有可能的橙子组合，直到凑出恰好w公斤，记录最小成本。但代码存在全局变量未正确声明的问题，导致无法更新最小成本，修正后的代码如下：

import math

res = math.inf

def solve(n, cost, w, curr_cost, stack):
    global res
    if w < 0:
        return
    if w == 0:
        print(stack, curr_cost)
        if curr_cost < res:
            res = curr_cost
        return
    for i in range(n):
        # 选择第i种橙子（重量为i+1公斤）
        stack.append(i + 1)
        solve(n, cost, w - (i + 1), curr_cost + cost[i], stack)
        stack.pop()  # 回溯，取消当前选择

n = 5
cost = [20, 10, 4, 50, 100]
w = 5
solve(n, cost, w, 0, [])
print(res)  # 输出14（2公斤+3公斤的组合：10+4=14）

该递归的逻辑：

• 每一步枚举所有可选的橙子重量，尝试加入当前组合
• 选中后，剩余采购重量减少对应公斤数，当前成本累加对应橙子的成本
• 若剩余重量为0，更新全局最小成本；若剩余重量为负，直接返回（无效组合）
• 回溯取消当前选择，继续尝试下一种橙子

暴力递归的缺陷是重复计算大量重叠子问题，比如凑3公斤的最小成本会被多次调用，因此需要用记忆化或自底向上动态规划优化。

二、子问题识别 #

动态规划的核心是找到重叠子问题和最优子结构：

1. 重叠子问题：计算dp[w]（凑w公斤的最小成本）时，需要依赖更小重量的子问题解dp[w - k]（k为可选橙子重量）
2. 最优子结构：dp[w]的最优解，等于所有dp[w - k] + cost[k-1]（cost[k-1]是k公斤橙子的成本）中的最小值

简言之，子问题就是计算0到w公斤中每个重量的最小采购成本，大重量的最优解完全由更小重量的最优解推导而来。

三、自底向上DP解决方案构建 #

可以用一维DP数组或二维DP表实现，以下分别详解：

1. 一维DP数组实现 #

一维数组dp中，dp[j]表示凑出恰好j公斤的最小成本。

• 初始化：dp[0] = 0（凑0公斤成本为0），其余dp[j] = 无穷大（初始状态下无法凑出对应重量）
• 状态转移：对每个重量j（从1到w），遍历所有可选橙子重量k（即i+1，i从0到n-1），若j >= k，则dp[j] = min(dp[j], dp[j - k] + cost[i])

代码实现：

import math

def min_cost(cost, w):
    n = len(cost)
    dp = [math.inf] * (w + 1)
    dp[0] = 0  # 基准情况：0公斤成本为0
    
    for j in range(1, w + 1):
        for i in range(n):
            k = i + 1  # 当前橙子的重量
            if j >= k and dp[j - k] != math.inf:
                dp[j] = min(dp[j], dp[j - k] + cost[i])
    
    return dp[w] if dp[w] != math.inf else -1  # 无法凑出时返回-1

cost = [20, 10, 4, 50, 100]
w = 5
print(min_cost(cost, w))  # 输出14

2. 二维DP表实现 #

你提到的n x w二维DP表中，dp[i][j]表示只用前i+1种橙子（重量1到i+1公斤），凑出恰好j公斤的最小成本。

初始化规则

• 第0行（仅用1公斤橙子）：dp[0][j] = cost[0] * j，只能用1公斤橙子凑j公斤，成本为单份成本乘以数量
• 第0列（凑0公斤）：dp[i][0] = 0，凑0公斤无需成本
• 第1列（凑1公斤）：所有行值均为cost[0]，因为只有1公斤橙子能凑出1公斤

状态转移规则

对于dp[i][j]（i从1到n-1，j从2到w），有两种选择：

• 不使用第i种橙子：成本等于dp[i-1][j]（只用前i种橙子的最优解）
• 使用第i种橙子：若j >= i+1，成本等于dp[i][j - (i+1)] + cost[i]（可重复使用当前橙子，因此取当前行的子问题解）
• 取两者的最小值作为dp[i][j]的结果

以示例中dp[2][5]（用1、2、3公斤橙子凑5公斤）为例：

• 不使用3公斤：dp[1][5] = 40（2次2公斤+1次1公斤）
• 使用3公斤：dp[2][5-3] + 4 = dp[2][2] +4 =10+4=14
• 最终dp[2][5] = min(40,14)=14，即最优解

二维DP代码实现：

import math

def min_cost_2d(cost, w):
    n = len(cost)
    dp = [[math.inf]*(w+1) for _ in range(n)]
    
    # 初始化第0行（仅用1公斤橙子）
    for j in range(w+1):
        dp[0][j] = cost[0] * j
    
    # 初始化第0列（凑0公斤）
    for i in range(n):
        dp[i][0] = 0
    
    # 填充DP表
    for i in range(1, n):
        k = i + 1  # 当前橙子的重量
        for j in range(1, w+1):
            # 选择1：不使用当前橙子，取上一行结果
            option1 = dp[i-1][j]
            # 选择2：使用当前橙子（若重量足够）
            option2 = math.inf
            if j >= k:
                option2 = dp[i][j - k] + cost[i]
            dp[i][j] = min(option1, option2)
    
    return dp[n-1][w] if dp[n-1][w] != math.inf else -1

cost = [20, 10, 4, 50, 100]
w = 5
print(min_cost_2d(cost, w))  # 输出14

四、子问题组合得到最终解 #

不管是一维还是二维DP，都是通过从小重量到大重量逐步计算，利用已解决的子问题最优解推导更大重量的解：

• 一维DP中，计算dp[j]时，所有dp[j-k]已经是凑j-k公斤的最小成本，加上当前橙子成本取最小值，即可得到dp[j]的最优解
• 二维DP中，每一行代表允许使用更多种类的橙子，通过对比“不用当前橙子”和“用当前橙子”的成本，逐步更新每个重量的最优解，最终右下角的dp[n-1][w]就是用所有橙子种类凑w公斤的最小成本

内容的提问来源于stack exchange，提问作者Learner