基于0/1背包逻辑的无限背包递归解法及思路探究

在我研究过的所有0/1背包和无限背包的动态规划解法里，常规思路其实挺直观的：

• 0/1背包的核心递归逻辑：针对第n个物品，我们只有两个选择——选或者不选，递归比较两种决策下的总价值，取最大值作为最优解。具体来说，要么把第n个物品放进背包（前提是剩余容量够装它），计算剩余容量下前n-1个物品的最大价值加上当前物品的价值；要么直接放弃这个物品，取前n-1个物品在原容量下的最大价值，两者取大即可。
• 无限背包的常规递归逻辑：因为物品可以重复选取，思路会灵活一些。常见的做法是，要么把第n个物品当作最后放入背包的项（这时候容量减去该物品重量后，依然可以继续考虑选第n个物品），要么最后放入的是前n-1个物品中的某一个，同样取这两种情况的最大值来推进递归。

不过我最近发现，无限背包其实也能套用0/1背包的核心「选/不选」逻辑，结合**最小值（min）**操作来实现递归求解，具体思路如下：

核心转化思路 #

我们可以把无限背包中「可重复选同一物品」的特性，转化为对单个物品的「有限次数选择」问题——毕竟背包容量是固定的，每个物品最多能选的次数是有限的：假设当前背包剩余容量为W，第n个物品的重量为w_n，那最多能选的次数就是k = min(W // w_n, 理论最大次数)（这里的min用来确保我们不会选到超过背包容量的数量）。

这时候，我们就可以把问题套入0/1背包的逻辑框架：对于第n个物品，我们可以选择选0个（对应0/1背包的「不选」），或者选1到k个中的任意数量（对应0/1背包中「选多个拆分后的物品」），递归计算所有可能情况的价值，取最大值。

递归实现的具体逻辑 #

我们定义递归函数 dp(n, W) 表示用前n个物品填充容量为W的背包能得到的最大价值，那么结合min操作的递归式可以写成：

def dp(n, W):
    if n == 0 or W == 0:
        return 0
    # 不选第n个物品的情况
    not_take = dp(n-1, W)
    # 计算最多能选多少个第n个物品
    max_count = min(W // weights[n-1], float('inf'))  # weights是物品重量数组，索引从0开始
    take = 0
    # 枚举选1到max_count个的情况，取最大价值
    for t in range(1, max_count + 1):
        if W - t * weights[n-1] >= 0:
            current = dp(n-1, W - t * weights[n-1]) + t * values[n-1]
            if current > take:
                take = current
    # 返回两种选择的最大值
    return max(not_take, take)

当然，这个枚举的方式可以进一步优化（比如用递推代替枚举，把dp(n, W)转化为max(dp(n-1, W), dp(n, W - w_n) + v_n)），但这里的核心是借助min操作确定单个物品的可选次数上限，把无限背包的问题转化为符合0/1背包「有限选择」逻辑的递归问题。

这种思路的好处是完全复用了0/1背包的核心思考逻辑，不需要重新构建全新的递归状态，对于理解两种背包问题的内在联系很有帮助。

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