不受限背包问题的递归解法，使用0/1背包的逻辑

Question

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

0/1 背包：通过选择第n个物品或排除第n个物品来最大化总价值。例如，0/1背包

无界背包：通过将第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.

但我无法证明我上述的解决方案不起作用。这个想法来自coin-change问题，其中你必须计算为给定金额找零的方法数，假设硬币的供应是无限的。

所以我的问题是，为什么我在这里提出的方法，从未用于无界背包或至少从未在任何地方提到过？有人可以帮我证明或证明这种方法吗？先谢谢了！

- user270386

---

先前的艺术品，我猜测是：https://www.geeksforgeeks.org/unbounded-knapsack-repetition-items-allowed/ - David Eisenstat

那就是唯一的原因吗？我给出的逻辑看起来不错吧？ - user270386

是的，看起来不错。 - David Eisenstat

这很有效。在这里，递归树中的每个父节点都有两个子节点，并且在每个容量处，应该有一个长度为len(items)的分支...每个分支实际上都是“对于items中的item”循环，可以从每个容量代替完成。如果您改为在每个容量处进行for循环，则最终每个父节点都会有len(capacity)个孩子。我猜你是在用一棵更高的树来换取一棵更胖的树。 - Bobby Battista

Answer 1

您提到的解决方案在任何地方都找不到，因为您的解决方案不是动态规划方法。在您的代码中，它重新评估了子情况，这在动态规划中不应该发生。 如果您想尝试，请使用此代码，与您的代码相同，但遵循动态规划规则。

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))

使用任何你喜欢的方法，但是要确保没有重复计算重叠的子问题。

- Confused Mind

Answer 2

在每次递归调用中，函数遍历所有可用的权重以查看是否可以包含，如果可以，则在当前递归调用中将其值累加到max_val中。在调用结束时，如果我们能够获得一个值，则返回一个标志，告诉我们已经找到了一个解决方案，并将maxSoFar设置为到目前为止的max_value。

#include<bits/stdc++.h>
using namespace std;

// Returns the maximum value with knapsack of
// W capacity
int unboundedKnapsack(int W, int n, int val[], int wt[], int &maxValue)
{
    // dp[i] is going to store maximum value
    // with knapsack capacity i.
    if( W == 0)
        return true;
    int maxSoFar = INT_MIN;
    bool foundASeries = false;
    for(int i = 0; i < n; i++)
    {
        if(W >= wt[i])
        {
            maxValue  = 0;
            if(unboundedKnapsack(W-wt[i], n, val, wt, maxValue))
            {
                foundASeries = true;
                maxSoFar = max(maxSoFar, maxValue + val[i]);
            }
        }
    }
    maxValue = maxSoFar;
    return foundASeries;
}

// Driver program
int main()
{
    int W = 8;
    int val[] = {10, 40, 50, 70};
    int wt[] = {1, 3, 4, 5};
    int maxValue = 0;
    int n = sizeof(val)/sizeof(val[0]);

    cout << unboundedKnapsack(W, n, val, wt, maxValue)<<endl;
    cout<< "max value is "<<maxValue;
    return 0;
}

- vivekanand chauhan

Answer 3

如果你将在无边界背包问题中使用这种方法，那么程序的空间复杂度将为O(n*W)；而如果你使用普遍给出的方法，它将为O(n+w)，其中n是物品数量，W是总重量。

- Chandan Tiwari