This story is a direct sequel to my previous post on Greedy Algorithms, so you may want to check that out first. It is still okay if you are only interested in Dynamic Programming and want to skip it since I will be explaining the problem again.

这个故事是我以前关于贪婪算法的上一篇文章的直接续集，因此您可能想先检查一下。 如果您只对动态编程感兴趣并且想跳过它，那还是可以的，因为我将再次解释问题。

When I was a university student, dynamic programming was the hardest topic in the Algorithms class for me. That was mainly because of being have to read long pages of redundant explanations prior to understanding the actual problem. That’s why in this post, instead of starting with a boring definition, I will directly jump into explaining the first problem of this section.

当我还是一名大学生时，对我来说，动态编程是算法课上最难的话题。 这主要是因为在理解实际问题之前必须阅读冗长的冗长解释。 这就是为什么在这篇文章中，我不会直接以无聊的定义开头，而是直接跳入解释本节的第一个问题。

背包问题 (Knapsack Problem)

Unlike the previous post, this time we talk about the 0–1 Knapsack Problem. Being part of the uprising movements against social injustice in government policies, you decided to gang up with some of your nerd friends in order to execute a bank job. Each gang member carries a bag with 50 kg capacity. Each of you hit the vault one by one and when it is finally your turn, you see that there is only one gold, one silver and one platinum bar left to take. You want to increase your gain as much as possible with your limited carrying capacity.

与上一篇文章不同，这次我们谈论的是0-1背包问题 。 作为政府政策中反对社会不公正现象的起义运动的一部分，您决定与一些书呆子朋友结盟，以执行银行工作。 每个团伙成员都可以携带一个50公斤的袋子。 你们每个人一个一个地撞击金库，最后轮到您时，您会发现只有一枚金，一枚白银和一枚白金条可供使用。 您想通过有限的承载能力来尽可能增加收益。

The gold bar weighs 20 kg and worth 1000 dollars

金条重20公斤，价值1000美元

The silver bar weighs 30 kg and worth 1200 dollars

银条重30公斤，价值1200美元

The platinum bar weighs 10 kg and worth 600 dollars

铂金棒重10公斤，价值600美元

If you calculate the price per kg for each bar, you will see that platinum is the most expensive, then gold, and finally silver is the cheapest. The greedy strategy in the previous post (fractional knapsack problem) tells you to always take the most profitable one per kg first. If you try applying the same strategy in this case, you will end up taking the platinum and gold bar, a total of 1600 dollars.

如果您计算每根酒吧的每公斤价格，您会发现铂金是最昂贵的，然后是黄金，最后是最便宜的白银。 上一篇文章中的贪婪策略(小背包问题)告诉您，始终要首先选择每公斤最赚钱的产品 。 如果在这种情况下尝试应用相同的策略，最终将获得铂金和金条，总计1600美元。

If you would have taken the gold and silver bars instead, you would have ended up with 2200 dollars, as you can see in the image above. So, the same greedy strategy that worked on the fractional knapsack problem did not give you the optimal solution for the 0–1 knapsack problem.

如果您选择使用金条和银条，则最终将获得2200美元，如上图所示。 因此，解决小背包问题的相同贪婪策略无法为您解决0–1背包问题的最佳解决方案。

This is happening because in the fractional case you were able to take as much as possible of each item to fill your bag. So your answer is only depending on a single parameter: money. But in the 0–1 case you have to decide whether to take it or leave for each item and compare the results of each possible permutation in order to find the most profitable one.

发生这种情况的原因是，在小部分情况下，您可以尽可能多地取出每个项目装满您的行李。 因此，您的答案仅取决于一个参数：金钱。 但是在0-1的情况下， 您必须决定是接受还是离开每个商品，并比较每个可能排列的结果，以找到最有利可图的商品。

You do this through recursion. But before we continue, let’s first consider a much simpler recursive algorithm.

您可以通过递归执行此操作。 但是在继续之前，让我们首先考虑一个更简单的递归算法。

斐波那契系列 (Fibonacci Series)

Ugh, this again… In high school, I remember being very impressed with the golden-ratio theories of Ancient Greece. After 10 years into computer science and now I look down on Fibonacci Series. Nevertheless, it is quite useful when you want to talk about recursion. Here is the formula:

gh，这又是……在高中时，我记得古希腊的黄金比率理论给我留下了深刻的印象。 在计算机科学领域工作了10年之后，现在我开始看不起斐波那契数列。 但是，当您要讨论递归时，它非常有用。 这是公式：

Fibonacci series is implemented with a simple recursive function:

Fibonacci系列通过简单的递归函数实现：

unsigned int fibonacci(unsigned int n) { if (n < 2) { return n; } return fibonacci(n - 1) + fibonacci(n - 2);}

Easy… This short function solves the Fibonacci series but there is a problem with this approach. Can you spot it? Go ahead and think for a while.

容易……这个简短的函数解决了斐波那契数列，但是这种方法存在问题。 你能发现吗？ 继续思考一会儿。

Did you find it? Good. If you couldn’t, do not worry. I’m sure you know the answer on some unconscious level: It is the recurring calculations. You calculate the result of the same subproblem over and over again, ending up with an exponential-time algorithm that makes me shiver to my bones when I consider larger inputs.

找到了吗 好。 如果您做不到，请不要担心。 我确定您在某种程度上已经知道答案了：这是经常性的计算 。 您一次又一次地计算相同子问题的结果，最后得到一个指数时间算法，当我考虑较大的输入时，该算法使我不寒而栗。

But why would you that? Why would you want to calculate the same result over and over and over again? I mean, that’s just plain stupid. Instead, why not store the result for fibonacci(x) and just use that value when you need it again? Now slap your face and scream dynamic programming!

但是你为什么呢？ 为什么要一遍又一遍地计算相同的结果？ 我的意思是，那简直就是愚蠢。 相反，为什么不为fibonacci(x)存储结果并在再次需要时使用该值呢？ 现在拍打脸，尖叫 动态编程 ！

We will apply this strategy to our code and store the results in an array. You can use any data structure depending on your needs. This technique is called memoization - why they didn’t just call memorization will forever haunt me.

我们将这种策略应用于我们的代码并将结果存储在数组中。 您可以根据需要使用任何数据结构。 这种技术被称为记忆 - 为什么他们不仅仅称呼记忆会永远困扰我 。

You can approach the overlapping subproblems from two sides: top-down or bottom-up. Here it the algorithm for the top-down approach:

您可以从两个方面来处理重叠的子问题： top-down或bottom-up 。 这里是自顶向下方法的算法：

// Note: Size is n + 1 because we store the values from 0 to nunsigned int lookup[n + 1] = {0};unsigned int fibonacci(unsigned int n) { if (n < 2) { return n; } else if (lookup[n] != 0) { return lookup[n]; } lookup[n] = fibonacci(n - 1) + fibonacci(n - 2); return lookup[n];}

All we have changed in the code was to introduce the lookup array and return the stored value if one such exists. Next, we see the bottom-up approach that turns the algorithm into an iterative function.

我们在代码中所做的更改只是引入了查找数组，如果存在这样的存储数组，则返回存储的值。 接下来，我们看到了自下而上的方法 ，该方法将算法转换为迭代函数。

unsigned int fibonacci(unsigned int n) { unsigned int lookup[n + 1] = {0}; lookup[0] = 0; lookup[1] = 1; for (unsigned int i = 2; i <= n; i++) { lookup[i] = lookup[i - 1] + lookup[i - 2]; } return lookup[i];}

Which method you will use is entirely up to you but the bottom-up approach generally performs better since there are no additional function calls. The top-down approach can be preferable if you don’t need to calculate the result for every single index in the array or your storage of preference. But if you need to calculate each one like in this example, I would go with the bottom-up approach. In any case, dynamic programming greatly increases the performance of the algorithm.

您将完全使用哪种方法完全取决于您，但是自下而上的方法通常效果更好，因为没有其他函数调用 。 如果您不需要为数组或偏好存储中的每个索引计算结果，则自上而下的方法可能更可取。 但是，如果您需要像本示例中那样计算每一个，我将采用自下而上的方法。 无论如何， 动态编程极大地提高了算法的性能。

Now let’s turn our attention back on the Knapsack Problem. We already saw that we need to go through all possibilities to find the optimum solution. Just like in Fibonacci series, we will use a divide and conquer method by recursively solving the problem for smaller bag sizes.

现在让我们把注意力转移到背包问题上 。 我们已经看到，我们需要尽一切可能找到最佳解决方案。 就像在斐波那契数列中一样，我们将通过递归解决较小袋子尺寸的问题来使用分而治之的方法。

The recursive algorithm for the 0–1 knapsack problem is a little bit more complicated, so let me elaborate first. The function has 3 parameters:

0–1背包问题的递归算法稍微复杂一点，所以让我先详细说明一下。 该函数具有3个参数：

vector<Item> items: The list of items waiting to be taken

vector <Item> items：等待获取的项目列表

int size: Remaining size (weight) of the bag

int size：袋子的剩余尺寸(重量)

int index: Index of the last processed Item in items

INT指数：在项目的最后处理项目的索引

We will process each item on the list one by one. For each item to be processed there are two possible cases: Either we take it or leave it behind. This means that there will be two recursive calls for each item representing whether or not we are taking it.

我们将一一处理清单上的每个项目。 对于每个要处理的项目，有两种可能的情况：我们要么接受它，要么将其抛在后面。 这意味着每个项目将有两个递归调用，分别代表我们是否要接受它。

If we take the item, we need to subtract its weight from the remaining capacity of the bag and add its price to our final profit.

如果我们拿走物品，我们需要从袋子的剩余容量中减去其重量，并将其价格加到我们的最终利润中。 If we don’t take it, we will move on to the next item without any changes to the remaining capacity or profit.

如果我们不接受，我们将继续进行下一个项目，而对剩余容量或利润没有任何更改。

There is also an extra case where we cannot steal the item since it is heavier than the remaining bag capacity. Finally, the algorithm stops either when

还有一种特殊情况，我们无法偷走该物品，因为它比剩余的行李容量重。 最后，算法会在以下情况下停止

There is no more capacity left in the bag

包里没有更多的容量了 All items are already processed

所有项目均已处理

The final C++ code is something like this:

最终的C ++代码是这样的：

int knapsack(vector<Item> items, int size, int index) { // Base case: either bag is full or we tried all items if (size == 0 || index == items.size()) { return 0; } // Current item weighs more than the remaining bag size Item current = items[index]; if (current.weight > size) { return knapsack(items, size, index + 1); } int weight = current.weight; int price = current.price; // a is the price when current item is taken // b is when it is not taken int a = price + knapsack(items, size - weight, index + 1); int b = knapsack(items, weight, index + 1); return max(a, b);}

It might be a little hard to read this recursion at first. If you are having a hard time understanding, just write it down and it will be clear.

一开始阅读此递归可能会有点困难。 如果您很难理解，只需将其写下来就可以了。

Now, this is just a recursive solution and it makes recurring calculations just like our Fibonacci function once did. In order to avoid that, we need to store the already calculated results in a 2D array.

现在，这只是一个递归解决方案，它像我们的斐波那契函数曾经做的那样进行重复计算。 为了避免这种情况，我们需要将已经计算的结果存储在2D数组中。

The most complicated part of this algorithm is how to store the results. An element lookupTable[i][j] corresponds to the result for the first i items processed for a bag with j kg capacity. You are going to read this sentence multiple times.

该算法最复杂的部分是如何存储结果。 元素lookupTable [i] [j]对应于容量为j kg的袋子处理的前i个项目的结果。 您将多次阅读此句子。

We can use the top-down recursive or bottom-up iterative approach. Remember when I said to use the top-down approach when you don’t really need to calculate every single case? It seems appropriate for this problem.

我们可以使用自上而下的递归或自下而上的迭代方法。 还记得我说过您不需要真正计算每个个案时使用自上而下的方法吗？ 似乎适合此问题。

// Note: This is not valid in C++ but you got the pointint lookupTable[count + 1][size + 1] = {-1};int knapsack(vector<Item> items, int size, int index) { // Base case: either bag is full or we tried all items if (size == 0 ||index == items.size()) { return 0; } // Result already calculated if (lookupTable[index][size] != -1) { return lookupTable[index][size]; } // Current item weighs more than the remaining bag size Item current = items[index]; if (current.weight > size) {lookupTable[index][size] = knapsack(items, size, index + 1); return lookupTable[index][size]; } int weight = current.weight; int price = current.price; // a is the price when current item is taken // b is when it is not taken int a = price + knapsack(items, size - weight, index + 1); int b = knapsack(items, weight, index + 1);lookupTable[index][size] = max(a, b); return lookupTable[index][size];}

The only thing that’s different from the recursive solution is the part we store the calculated values in a 2D array and simply return it if one such exists. For any DP problem, I strongly advise you to write the recursive algorithm first and then the memoization step should be easy.

与递归解决方案唯一不同的是，我们将计算值存储在2D数组中，如果存在则将其简单地返回。 对于任何DP问题，我强烈建议您先编写递归算法，然后简化记忆步骤。

That’s it. I know this one is a little bit complicated but just try to understand the idea behind it and you will be doing okay.

而已。 我知道这有点复杂，但是只要尝试了解其背后的想法，您就可以了。

Oh, wait! I forgot to define what dynamic programming is. Dynamic programming is a technique that allows you to divide your problem into smaller subproblems and store the result of the subproblems in order to be able to use them at recurring calculations.

等一下！ 我忘记定义什么是动态编程。 动态编程是一种技术，它使您可以将问题分成较小的子问题，并存储子问题的结果，以便能够在重复计算中使用它们。

It is not helpful at this point, huh? Well then, see you in the next part…

此时没有帮助，是吗？ 好吧，下一部分再见...

翻译自: https://medium.com/swlh/algorithms-revisited-part-2-dynamic-programming-9a645f8b11f0