时间戳

首页 > 解决方案 > 使用0/1背包的逻辑递归解无界背包

algorithm - 使用0/1背包的逻辑递归解无界背包

问题描述

在我检查过的 0/1 背包和无界背包的所有 DP 解决方案中，解决方案的方法总是这样定义：

0/1 背包：通过取第 n 项或排除第 n 项来最大化总价值。例如， 0/ 1 背包

unbounded knapsack：通过将第 n 个项目视为最后一个拾取的项目，或 (n-1) 个项目作为最后一个拾取的项目等来最大化总价值。例如，无界背包

但是无界背包也可以使用 0/1 背包的逻辑稍作调整来解决。我的意思是，对于 0/1 背包，我们执行以下操作（使用第一个链接中的代码）：

return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
            knapSack(W, wt, val, n-1)
          );

请注意，在我们包含的情况下，我们如何将wt[n-1]数组的大小减少 1。这意味着wt[n-1]现在已经用尽，因此不能再次使用。但是，如果在无限情况下，我们不会将数组大小减小 1（这意味着wt[n-1]可以再次使用），那么稍微修改一下递归关系就可以了：

return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n),
            knapSack(W, wt, val, n-1)
          );

为什么这种无界背包的方法从来没有在任何地方提到过呢？实际上这里特别说明，我们不能使用与 0/1 背包相同的逻辑来处理无界的。摘自该链接：

Observation:
I can never exhaust any item because there are an unbounded supply of items.
Therefore:
The technique used in the 0,1 knapsack problem cannot be used.

但我无法反驳我上面提到的解决方案不起作用。这个想法来自硬币找零问题，假设硬币供应无限，你必须计算给定数量的找零方法的数量。

所以我的问题是为什么我在这里提出的方法从未用于无限背包或至少从未在任何地方提及？谁能帮我证明或反驳这种方法？提前致谢！

标签： algorithmdynamic-programmingknapsack-problem

解决方案

您不会在任何地方找到您提到的解决方案，因为您的解决方案不是动态编程方法。在您的代码中，它是重新评估在动态编程中不应该发生的子案例。如果您愿意，您可以尝试此代码，与您的代码相同，但它遵循动态编程规则


def UnboundedKnapSack2(wt, val, n, capacity):
    global dp
    if dp[n][capacity] != -1:
        return dp[n][capacity]
    else:
        if n == 0 or capacity <= 0:
            dp[n][capacity] = 0
            return dp[n][capacity]
        elif wt[n - 1] <= capacity:
            dp[n][capacity] = max(
                val[n - 1] + UnboundedKnapSack(wt, val, n, capacity - wt[n - 1]),
                UnboundedKnapSack(wt, val, n - 1, capacity),
            )
            return dp[n][capacity]
        else:
            dp[n][capacity] = UnboundedKnapSack(wt, val, n - 1, capacity)
            return dp[n][capacity]

weight = [1, 3, 4, 5]
values = [10, 40, 50, 70]
capacity = 8
dp = [[-1 for i in range(capacity + 1)] for j in range(len(weight) + 1)]
print(UnboundedKnapSack2(weight, values, len(weight), capacity))

这不是您问题的唯一解决方案，还有其他根本不使用递归的动态编程代码。

def UnboundedKnapSack3(wt, val, capacity):
    n = len(wt)
    dp = [[0 for i in range(capacity + 1)] for j in range(n + 1)]
    for i in range(n + 1):
        for j in range(capacity + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif j >= wt[i - 1]:
                dp[i][j] = max(val[i - 1] + dp[i][j - wt[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[-1][-1]


print(UnboundedKnapSack3([1, 3, 4, 5], [10, 40, 50, 70], 8))

使用你喜欢的任何一个，但确保不应该重新计算重叠的子问题。

推荐阅读