c++货郎担问题代码实现

这是一个货郎担问题的代码实现：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if j < weights[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

其中，`weights` 是每个物品的重量列表，`values` 是每个物品的价值列表，`capacity` 是货郎担的最大容量。函数返回的是最大价值。

该函数使用了动态规划的思想，创建了一个二维数组 `dp`，其中 `dp[i][j]` 表示前 `i` 个物品放入容量为 `j` 的背包中所能获得的最大价值。依次计算 `dp[i][j]` 的值，最后返回 `dp[n][capacity]`，即前 `n` 个物品放入容量为 `capacity` 的背包中所能获得的最大价值。

参考链接：https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html