理解背包暴力程序

Question

朋友给了我一个Knapsack暴力破解程序，想了解下。这是我得到的代码：

def knapSack(W, wt, val, n):

    if n == 0 or W == 0:
        return 0


    if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)


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




values = [10, 500, 786]
wt = [1, 2, 0.5]
weight = 2
n = len(values)
print(knapSack(weight   , wt, values, n))

我不明白这是怎么回事：

if (wt[n - 1] > W):
return knapSack(W, wt, val, n - 1)

我也不明白这是怎么回事：

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

TBH 我对这两条线路的工作原理一无所知，它们看起来像是随机调用背包。我也不明白n-1是干什么的

我知道这个请求很含糊抱歉:)

Answer 1

背包问题的基础是这样的：给定一组物品，每件物品都有一个价值和一个重量，找到给定重量限制下最有价值的物品组合。

这些是你问题中的变量（顺便说一句：你朋友的命名约定真的很糟糕）。

这个问题有两种极端情况：

没有剩余物品
没有剩余重量

程序如何解决这些问题？

if n == 0 or W == 0:
        return 0

第二段代码是另一种情况

正在测试的项目超出重量限制

if (wt[n - 1] > W):
        return knapSack(W, wt, val, n - 1)

这只是意味着尝试对背包算法进行另一次迭代，同时移除当前正在测试的物品。

这里的 else 块是拼图的最后一块

被测物品未超过重量限制

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

这到底在说什么？ Return两个选项中的最大值：

当前物品的价值+重新执行背包算法的价值下限重量（W-wt[n-1]部分）和排除的物品（n-1部分） ).
排除当前物品的背包算法，重量限制相同（假设当前物品很重，但不值钱，这个选项可能会更高）。

这行得通，因为你实际上是在说取这个项目的价值，添加它，调整权重，看看剩下的最佳组合是什么，或者不包括这个项目，看看剩下的最佳组合是什么是。这将测试所有可能的子选项组合。

这整件事是被称为 Dynamic Programming 的范例的一个例子。我建议阅读它以获取与此类似的一些更简单的问题示例。一旦你理解了解决这些问题的方法，理解它们就会变得容易得多。

Answer 2

以上并不是严格意义上的动态规划。在 DP 中有一个 table 并且代码没有可能达到 Python 中的递归深度限制。

def unboundedKnapsack(W, n, val, wt):

    dp = [0 for i in range(W + 1)]

    ans = 0

    for i in range(W + 1):
        for j in range(n):
            if (wt[j] <= i):
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j])

    return dp[W]

W = 60
val = [ 1, 20]
wt = [1, 30]


n = len(val)

print(unboundedKnapsack(W, n, val, wt))

理解背包暴力程序

Making sense of Knapsack brute force program

python

parameters

knapsack-problem