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

在每次递归调用中，该函数都会迭代所有可用的权重以查看是否可以包含它，如果可以，则将其值累加到当前递归调用的 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;
}