没有重复的背包：最大数量的黄金 - Python 代码问题

Question

来自 Coursera 的算法工具箱课程。

问题介绍

给你一组金条，你的目标是尽可能多地把金条装进你的包里。每个柱子只有一个副本，对于每个柱子，您可以接受或不接受（因此您不能接受一小部分柱子）。

问题描述

任务。给定金条，求一袋容量为的最大黄金重量。输入格式。输入的第一行包含背包的容量和金条的数量。下一行包含整数 0,1, 。 . . ,−1 定义金条的重量。

约束。 1 ≤ ≤ 10^4； 1≤≤300； 0 ≤ 0, . . . , −1 ≤ 10^5.

输出格式。输出容量为 .

的背包能装下的最大黄金重量

我在 Python 中使用动态规划的解决方案：

def optimal_weight(W, w):

    golds = [0] + w
    gold_dict = {}
    for i in range(0, W+1):
        gold_dict[(i, golds[0])] = 0
    for i in golds:
        gold_dict[(0, i)] = 0

    for i in range(1, len(golds)):
        for weight in range(1, W+1):
            gold_dict[(weight, golds[i])] = gold_dict[(weight, golds[i-1])]
            if golds[i] <= weight:
                val = gold_dict[(weight-golds[i], golds[i-1])] + golds[i]
                if gold_dict[(weight, golds[i])] < val:
                    gold_dict[(weight, golds[i])] = val

    return max(gold_dict.values())

第二个输入是金条列表，其重量为整数。对于输入：

10, [1, 4, 8]

结果应为整数 9（即 1+8）。

我已经测试了一系列示例，其中包括一些极值，例如：

1, [0]

对于他们所有人来说，结果似乎都是正确的。但是，最终测试一直显示由于错误答案而未通过其中一项测试。因此我的代码中一定有错误。但是我很难找到它。（作业测试不会释放测试参数，因此我无法得到触发错误答案的输入）

有人能告诉我潜在的问题是什么吗？即使是提示也会非常感激。非常感谢。

编辑：

我添加了 main 函数来显示如何读取输入，但我不认为它链接到潜在的错误：

if __name__ == '__main__':
    input = sys.stdin.read()
    W, n, *w = list(map(int, input.split()))
    print(optimal_weight(W, w))

sys.stdin 将读取带有示例输入的测试 txt 文件，如下所示：

10 3
1 4 8

即一袋容量为10，金条3条，重量分别为1、4、8。

题中自带的main方法，未修改

Edit2 答案：

感谢以下 Arty 的建议，问题来自使用 gold[i] 作为 gold_dict 的元组键的一部分。如果有多根重量相同的金条，它们在 gold[] 列表中的索引将不同（不同的 i），但它们的 gold[i] 值将相同。在这种情况下，元组键 (weight, gold[i]) 可能会引用错误的对象。

我用错误的代码对 Arty 的正确代码进行了随机测试，以找到可能触发错误的参数，该错误在运行 ~3000 次后出现：

209 38
16, 21, 21, 96, 129, 144, 159, 253, 254, 259, 259, 267, 285, 290, 304, 351, 351, 383, 411, 429, 493, 494, 527, 530, 534, 596, 619, 625, 692, 717, 727, 727, 745, 772, 833, 853, 856, 946

对于这个例子，我的代码将得到答案 208，而正确答案是 202。

修复其实很简单，只需将所有键元组的 gold[i] 更改为 i 即可：

def optimal_weight(W, w):

    golds = [0] + w
    gold_dict = {}
    for i in range(0, W+1):
        gold_dict[(i, 0)] = 0
    for i in range(0, len(golds)):
        gold_dict[(0, i)] = 0
    for i in range(1, len(golds)):
        for weight in range(1, W+1):
            gold_dict[(weight, i)] = gold_dict[(weight, (i-1))]
            if golds[i] <= weight:
                val = gold_dict[(weight-golds[i], i-1)] + golds[i]
                if gold_dict[(weight, i)] < val:
                    gold_dict[(weight, i)] = val
    return max(gold_dict.values())

Answer 1

我使用布尔数组 d 实现了我自己的解决方案，元素 d[i][j] 是 True 当且仅当权重 j 可以通过 taking/not-taking 指数为 0 至 i 的黄金。我们从仅包含 j = 0 的 True 行开始，即权重 0 可以通过不取任何东西来组成。下一行的计算如下 - 如果 d[i - 1][j] 为 True（对应于不获取当前黄金）或如果 d[i - 1][j - golds[i]] 为 True（对应于获取当前黄金），则元素 d[i][j] 为 True .

关于您的解决方案。我建议在你的算法中做下一个修正，dict gold_dict 的键应该有第二个元素等于金条的索引，而不是金条的值，即你需要使用而不是 gold_dict[(weight, gold[i])]无处不在 gold_dict[(weight, i)]，尝试进行此更正，也许您的代码适用于所有测试！您已更正此建议 code is here。

我的解决方案代码如下：

Try it online!

def optimal_weight(W, golds):
    # We can compose weight 0 by taking nothing
    d = [[True] + [False] * W]
    for i in range(len(golds)):
        # We copy previous row which corresponds to
        # solution of not taking current gold
        d.append(d[-1][:])
        for w in range(golds[i], W + 1):
            # Weight w can be composed either by not taking current
            # gold (d[-2][w]) or by taking it (d[-2][w - golds[i]])
            d[-1][w] = d[-2][w] or d[-2][w - golds[i]]
        # It is enough to keep only last row
        d = d[-1:]
    for w in range(W, -1, -1):
        # Return maximal weight w that has True in d
        if d[-1][w]:
            return w
    
if __name__ == '__main__':
    import sys
    W, n, *w = list(map(int, sys.stdin.read().split()))
    print(optimal_weight(W, w))

输入：

10 3
1 4 8

输出：

没有重复的背包：最大数量的黄金 - Python 代码问题

Knapsack without repetitions: Maximum Amount of Gold - Python code question

python

knapsack-problem