用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.

但是我不能反驳我上面提到的解决方案是行不通的。这个想法来自硬币兑换问题，在这个问题中，假设硬币的供应量是无限的，你必须计算出改变给定数量的方法。

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

Answer 1

如果你在无界背包中使用这种方法，那么程序的空间复杂度将是O（n*W），如果你使用到处都给出的方法，那么它将是O（n W），其中n是项数，W是总重。

Answer 2

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

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

使用您喜欢的方法，但确保不应重新计算重叠的子问题。

Answer 3

在每个递归调用中，函数都会遍历所有可用的权重，以查看是否可以包含它，如果可以，则其值将累积到当前递归调用的max\u val中。在调用结束时，如果我们能够获得一个值，那么它将返回一个标志，告诉我们找到了一个解决方案，并将maxSoFar设置为max\u值。

#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;
}