我正在自学基本的编程原理,但我陷入了一个动态编程问题。让我们以臭名昭著的背包问题为例:
给定一组项目,每个项目都有一个权重和一个值,确定要包含在集合中的每个项目的计数,以便总权重小于或等于给定限制并且总值尽可能大。
让我们将重量限制设置为 10,并给出两个列表:weights = [2,4,7] 和 values = [8,4,9](我只是编造了这些)。我可以编写代码以在给定约束的情况下给出最大值——这不是问题。但是,如果我想知道我最终使用了哪些值呢?不是总价值——个别价值。所以对于这个例子,最大值将是权重为 2 和 7 的对象,总值为 8 + 9 = 17。我不希望我的答案读为“17”——我想要一个列表的输出比如:(8, 9)。这个问题可能很容易,但我正在处理的问题使用更大且具有重复数字的列表(例如,多个对象的值为 8)。
让我知道是否有人能想到任何事情。一如既往,对社区充满爱和感激。