背包暴力计划的意义

Question

一个朋友给了我一个背包蛮力程序，我想了解。我得到的密码是：

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

我不明白这是怎么回事：

^{pr2}$

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

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

我不知道这两条线是怎么工作的，它们看起来像是背包的随机调用。我也不明白n-1的作用。在

我知道这是一个相当模糊的请求对不起：）

Answer 1

以上并不是严格意义上的动态规划。在DP中有一个表，代码不可能达到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))

Answer 2

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

这些都是你问题中的变量（顺便说一句：你朋友的命名习惯很糟糕）。在

此问题有两种终端情况：

1. 没有剩余项目

2. 无剩余重量

该计划如何解决这些问题？在

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

第二段代码是另一种情况

被测物品超过重量限制

^{pr2}$

这只意味着在删除当前测试项目的情况下尝试另一次背包算法迭代。在

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

测试项目未超过重量限制

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

这到底在说什么？最多返回两个选项：

1. 当前项目的值+再次执行背包算法得到的值（权重下限为W-wt[n-1]部分）和排除的项目值（n-1部分）。

2. 不包括当前项目的背包算法和权重限制相同（假设当前项目很重，但价值不大，此选项可能会更高）。

这是因为你实际上是在说接受这个项目的值，加入它，调整权重，看看什么是最好的剩余组合，或者不包括这个项目，看看什么是最好的剩余组合。这将测试所有可能的子选项组合。在

这整件事就是一个被称为Dynamic Programming的范例。我建议你仔细阅读一下，找到一些类似这个问题的简单例子。一旦你摸索出解决这些问题的方法，理解它们就会变得容易得多。在