动态编程和0/1背包 [英] Dynamic Programming and the 0/1 knapsack
问题描述
即使我已经阅读了很多试图理解的资源，我在理解动态编程时还是遇到了一些麻烦。
我了解动态编程的示例使用斐波那契算法。我了解如果您使用分治法来解决问题，那么最终将多次解决一些子问题，而动态编程则通过解决这些重叠的子问题而仅解决一次（并将它们存储以供将来参考）来解决这一问题。 。但是，我在班级中以0/1背包问题为例向我介绍了动态编程，但我并不真正理解该示例，也不了解该示例如何说明动态编程，或者无论如何它都与fibonacci示例相似
以下是与此相关的幻灯片：
我主要了解直到上一张幻灯片的内容，其中说f（i，y）= max {....}
我到底找到了什么？为什么我什么都找不到？最重要的是，这与动态编程有什么关系？我不了解这种关系，就象斐波那契例子一样。老实说，我不知道这个背包问题与动态编程有什么关系，因为无论如何它似乎都无法与用斐波那契例子说明动态编程相提并论。就像我看不到任何相似之处或任何东西，对我来说真的没有多大意义
动态编程只是用更简单的子问题来定义问题。
在斐波那契的情况下，我们用两个较小的术语来定义问题。
在这种情况下，我们用一些项目和一些容量来定义问题，这些问题包含的项目较少且容量可能较小。
f（i，y）是包含项目 i 到 n ，容量为 y 。
现在我们可以将其定义为包含或排除项目 i ，然后获取项目 i + 1 到 n 。
当我们排除项目 i ，这不会改变权重，所以我们只看相同容量的最大利润，即 f（i + 1，y），利润也不会改变。
当我们添加项目时 i ，这会改变权重，特别是根据项目 i 的权重，即 w_i ，因此我们必须查找 f（i + 1，y-w_i）。但是然后我们也从项目 i 中获得利润，因此我们需要添加其利润，即 p_i 。
现在，由于我们要获得最大的利润，因此必须找到这两个值中的最大值，从而得出：
f（i，y）= max {f（i + 1，j），f（i + 1，y-w_i）+ p_i}
如果您仍然难以理解它，我建议您为自己构建一个示例以进行练习-无需过多解释就可以看到的措施它确实有效，并以此来理解为什么我们以这种方式做事。
I'm having some trouble understanding dynamic programming, even though I've read through so many resources trying to understand.
I understand an example given of dynamic programming using the fibonacci algorithm. I understand how if you use the divide and conquer approach to it, you'll end up solving some sub-problems multiple times, and dynamic programming takes care of that by solving those overlapping subproblems but only once (and storing them for future reference). However, I have been introduced to dynamic programming in my class using the 0/1 knapsack problem as an example, and I don't really understand the example, or how it illustrates dynamic programming, or how it's in anyway similar to the fibonacci example.
Here are the slides related to it:
I mainly understand what is going on until the last slide, where it says f(i,y) = max{....}
What exactly am I finding the max of? Why am I finding the max of anything at all? And most importantly, what does this have to do with dynamic programming? I don't understand the relation, like I do when it comes to the fibonacci example. I honestly have no clue what this knapsack problem has anything to do with dynamic programming because it doesn't even seem comparable in anyway to using the fibonacci example to illustrate dynamic programming. Like I don't see any parallels or anything at all, and it really doesn't make much sense to me
Dynamic programming is just defining the problem in terms of simpler subproblems.
In the case of Fibonacci, we define the problem in terms of the two smaller terms.
In this case, we define the problem with some number of items and some capacity in terms of problems containing less items and possibly a smaller capacity.
f(i,y) is the maximum profit containing items i through n with a capacity of y.
Now we can define this as either including or excluding item i, and then getting the maximum profit for items i+1 through n.
When we exclude item i, this doesn't change the weight, so we can just look at the maximum profit for the same capacity, i.e. f(i+1, y), and the profit also doesn't change.
When we include item i, this changes the weight, specifically by the weight of item i, which is w_i, so we have to look up f(i+1, y - w_i). But then we also get the profit from item i, so we need to add its profit, i.e. p_i.
Now, since we want the maximum profit, we have to find the maximum of these two values, giving us:
f(i, y) = max{f(i+1, j), f(i+1, y - w_i) + p_i}
If you're still having trouble understanding it, I suggest you construct yourself an example to work through - no amount of explaining quite measures up to seeing it actually working, and using this to get some intuition for why we do things the way we do.
这篇关于动态编程和0/1背包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
