跟踪动态规划步骤
我正在自学基本的编程原理，但我陷入了动态编程问题。让我们以臭名昭著的背包问题为例：
给定一组物品，每个物品都有一个重量和一个值，确定要包含在集合中的每个物品的数量，以便总重量小于或等于给定的限制和总价值尽可能大。
让我们将权重限制设置为 10，并给出两个列表：权重 = [2,4,7] 和值 = [8,4,9]（我刚刚编写了这些）。我可以编写代码来给出给定约束的最大值——这不是问题。但是如果我想知道我实际最终使用了哪些值呢？不是总价值——而是个体价值。因此，对于这个例子，最大值是权重为 2 和 7 的对象，总价值为 8 + 9 = 17。不过，我不希望我的答案读为“17”——我想要一个列表的输出例如：(8, 9)。这个问题可能很容易，但我正在解决的问题使用更大并且具有重复数字的列表（例如，多个对象的值为 8）。
如果有人能想到什么，请告诉我。一如既往，对社区充满爱和感激。
I'm teaching myself basic programming principles, and I'm stuck on a dynamic programming problem. Let's take the infamous Knapsack Problem:
Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Let's set the weight limit to 10, and let's give two lists: weights = [2,4,7] and values = [8,4,9] (I just made these up). I can write the code to give the maximum value given the constraint--that's not a problem. But what about if I want to know what values I actually ended up using? Not the total value--the individual values. So for this example, the maximum would be the objects with weights 2 and 7, for a total value of 8 + 9 = 17. I don't want my answer to read "17" though--I want an output of a list like: (8, 9). It might be easy for this problem, but the problem I'm working on uses lists that are much bigger and that have repeat numbers (for example, multiple objects have a value of 8).
Let me know if anyone can think of anything. As always, much love and appreciation to the community.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
将每个部分解决方案视为一个节点。只需将您使用的任何内容添加到每个节点中，最后成为答案的节点都将包含您使用的项目集。
因此，每次找到新的解决方案时，只需将项目列表设置为新的最佳解决方案的项目列表，然后对每个解决方案重复此操作。
Consider each partial solution a Node. Simply add whatever you use into each of these nodes and whichever node becomes the answer at the end will contain the set of items you used.
So each time you find a new solution you just set the list of items to the list of items of the new optimal solution and repeat for each.
基本的数组实现可以帮助您跟踪哪些项目启用了新的 DP 状态以获得其值。例如，如果您的 DP 数组是
w[]，那么您可以有另一个数组p[]。每次为w[i]生成状态时，您都将p[i]设置为用于获取“w[i]”的项目。然后要输出用于w[n]的项目列表，输出p[n]，然后移动到索引n-weightOf(p[n ])直到达到 0 即可输出所有项目。A basic array implementation can help you keep track of what items enabled a new DP state to get it's value. For example, if your DP array is
w[]then you can have another arrayp[]. Every time a state is generated forw[i], you setp[i]to the item you used to get to 'w[i]'. Then to output the list of items used forw[n], outputp[n], and then move to the indexn-weightOf(p[n])until you reach 0 to output all the items.