python - 没有重复的背包 : Maximum Amount of Gold - Python code question

Question

来自 Coursera 的算法工具箱类(class)。

问题介绍

您得到一组金条，您的目标是尽可能多地将金条放入包中。每个柱子只有一个副本，对于每个柱子，您可以接受或不接受(因此您不能接受一小部分柱子)。

问题描述

任务。给定 𝑛 金条，找出一袋容量 𝑊 能装下的最大黄金重量。输入格式。输入的第一行包含背包的容量 𝑊 和金条的数量 𝑛。下一行包含 𝑛 个整数 𝑤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

我使用 bool 数组 d 实现了自己的解决方案，元素 d[i][j] 为 True 当且仅当权重j 可以通过获取/不获取索引为 0 到 i 的金子以某种方式组成。我们从仅包含 True 的 j = 0 行开始，即权重 0 可以通过不取任何东西来组成。下一行的计算如下 - 如果 d[i - 1][j] 为 True，则元素 d[i][j] 为 True(这对应于不采用当前黄金)或如果 d[i - 1][j - golds[i]] 为真(对应于获取当前黄金)。

关于您的解决方案。我会建议在你的算法中做下一个修正，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

输出:

9