Backpack nine speak

The knapsack problem is one of the most classical problems in dynamic programming. It can be said that the complete understanding of the knapsack problem can greatly help us understand the basic derivation of the transfer equation of dynamic programming. The classic lecture on backpack problem is “Nine Lectures on Backpack” written by Cui Tianyi from Zhejiang University. This article is my notes and thoughts during reading this article.

In fact, the idea of dynamic programming is not difficult to think of. Most problems can be solved by moving gauge only at a glance. The difficulty lies in how to deduce the appropriate state matrix and state transition equation. This requires us to write more DP table, carefully find the rule.

Basic concepts of dynamic programming problems

The dynamic programming approach looks for definitions of states and state transition equations that conform to the “optimal substructure”. Once found, the problem can be solved by “memorizing the recurrence”. And finding the definition is the essence of dynamic programming.

Generally speaking, when the problem has the following three characteristics, dynamic programming method is applicable to solve:

• Optimal substructure: The optimal solution of a large problem can be derived from the optimal solution of a small problem
• No aftereffect: If the state of a stage is given, the development of the process after that stage is not affected by the states prior to that stage.
• Overlapping subproblems: The same subproblem may be solved more than once

In fact, the first two characteristics mentioned above are precisely characteristics of the divide-and-conquer algorithm. Both dynamic programming and recursive algorithms are essentially subsets of divide-and-conquer algorithms, which break down big problems into smaller ones to solve. The third feature distinguishes the use of recursion from the use of dynamic programming: generally speaking, we can use recursive algorithm to solve the independent subproblems, while dynamic programming must be used for the overlapping subproblems, otherwise the time complexity will be greatly increased.

Let’s take the simplest Fibonacci number column. When solving the 101st term, we need to compute the 100th and 99th terms, and when solving the 102nd term, we need to compute the 100 and 101st terms. If we went straight to the recursive algorithm, solving the 101st and 102nd terms would repeat the 100th term twice, wasting a lot of time.

In fact, if we modify the recursive algorithm a little bit, we can make it in the form of dynamic programming, that is, adding another data structure for memory. This practice is called mnemonic search, and it is essentially a top-down dynamic programming algorithm (from big problems to small problems). This is also a dynamic programming approach (bottom-up) if we start solving small problems and end up recursing the results required for big problems. A number of blogs distinguish between mnemonic search and bottom-up dynamic programming, which I actually think are different implementations of dynamic programming.

If we use the dynamic programming algorithm, it will get the result of the 100th item during the calculation, so as to avoid double calculation, which is why the dynamic programming algorithm can greatly reduce the running time.

The key points of dynamic programming algorithm are summarized as follows:

• Dynamic programming attempts to solve each subproblem only once
• Once the solution of a given stator problem has been calculated, it is memorized and stored so that the next time the same subproblem solution is needed, the table can be looked up directly.

Dynamic programming algorithm is often compared with greedy algorithm, but greedy algorithm only focuses on the local optimal solution, when the local optimal cannot reach the global optimal, greedy algorithm will make mistakes. In fact, how to choose various strategies can be summarized as follows:

There is only one state per stage -> recursion; The optimal state of each stage is derived from the optimal state of the previous stage -> greedy; The optimal state of each stage is obtained from the combination of states of all previous stages -> search; The optimal state of each phase can be obtained directly from one or more states of the previous phase regardless of how the previous state was obtained -> dynamic programming.Copy the code

At the same time, we should also note that although dynamic programming has no aftereffect, it does not mean that we can not use dynamic programming to solve the problems that need to acquire process combinations, such as: 140. Word split II.

0-1 backpack problem

The title

There are N items and a backpack of capacity V. The cost of putting in the ith item is C1i, and the value is Wi. Figure out which items to pack into the backpack maximize the sum of values.

The basic idea

The most basic backpack problem, each item only 1, and only one choice: put or not put.

We can define the state matrix: F[I, V] represents the maximum value of the first I items that can be obtained by placing them into a backpack of capacity V. Then its state transition equation is:

F (I, v) = maxF [] I – 1, v, F [I – 1, v – Ci] + Wi

A simple analysis of the above equation: given the backpack capacity v, the subproblem of the maximum value of the first I items into the backpack only needs to consider whether the ith item is put into the backpack. If the current item is not put into the backpack, the current value is equal to the total value of the previous I-1 item in the backpack with capacity V. However, if it is put into the backpack, the items left for the former I-1 will be reduced, and the current total value is equal to the total value of the backpack with the capacity v−Ci of the former I-1 item plus the current item value Wi. ** We convert the subproblem “the maximum value of the first I items into the backpack given the backpack capacity V” into the subproblem related only to the first I-1 items. ** At the same time, we use a two-dimensional array to store the state matrix F[I, V], which reduces the time of repeated calculation caused by overlapping subproblems.

Spatial complexity optimization

The space complexity of the above problems is O(VN), the time complexity has reached the optimal, but there is an optimization space in the space complexity.

By observing the state transition matrix, we find that the state of the ith item often depends only on the state of the i-1 item. Then we can easily think of using only a two-line array to store the state of two moments. Each time we update to the I +1 item, we let the state of the I item overwrite the state of the i-1 item. Let the state of the current item fill the second array. This method is called the scrollarray method.

However, we can further optimize to use only one array to represent the state. Observing the state transition equation, we find that F[I, v] is only related to F[i-1, V] and F[i-1, V-C], that is, the number of columns of the substates on which the current state depends must be less than or equal to the current state (v and V-C). That is, when “fill in the DP table”, the current row always refers to the “overhead” and “upper-left” positions of the row above it. So we can just open a one-dimensional array and fill in the table from back to front.

We need to update the state backwards because we need to use the previous state. If the state F[i-1,v] is updated backwards, the original state F[i-1,v] will be overwritten by the new state F[I,v], so that it cannot be found when F[i-1,v] is needed later, resulting in calculation errors.

By state compression, we can optimize the spatial complexity to O(V) and solve the 01 knapsack problem with only one array F[V].

• Space complexity: O(VN)
• Time complexity: O(V)

Initialization details

In the knapsack problem that we’ve seen for optimal solutions, there are actually two very different ways of asking. Some problems ask for the optimal solution when the backpack is exactly full, while others don’t ask for the backpack to be full. One difference between the two methods is that they are implemented differently at initialization.

If F[0] is required to be exactly full of knapsack, all F[1..V] except F[0] is set to −∞ during initialization, which can ensure that the final F[V] is an optimal solution that is exactly full of knapsack.

If you do not require the backpack to be full, but want the price to be as high as possible, you should set F[0..V] all to 0 when initializing. Why is that? To put it this way: the initialized F array is actually the legal state when nothing can be put into the backpack. If the backpack is exactly full, then only the backpack with the capacity of 0 can be “exactly full” in the case of nothing and value of 0, the other capacity of the backpack have no legal solution, belongs to the undefined state, should be assigned to -∞. If the backpack does not have to be full, then the backpack of any size has a legal solution of “nothing,” which has a value of zero, so the initial state values are all zero.

A sample

An example of the 01 knapsack problem is: 416. Segmentation and subset

The problem with this problem is: given a non-empty array containing only positive integers. Is it possible to split this array into two subsets so that the sum of the elements in the two subsets is equal?

This problem requires an equivalent conversion: can we pick positive integers from the array such that the sum of these numbers is equal to half of the sum of the entire array elements? The prerequisite is that the sum of the array must be even, that is, the sum of the array must be divisible by 2, which is a special rule. We will the abstraction of 01 knapsack problem: every positive integer can be thought of as a value equal to the weight of goods, assuming that there is a maximum capacity of binary array elements combined bag, can choose a few items, whether to fill the bag, also is the total value of these items is equal to the maximum capacity.

The code for solving the 01 knapsack problem is as follows:

class Solution:
    def canPartition(self, nums: List[int]) - >bool:        
        c=sum(nums)
        if c%2! =0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]# State compression
        for j in range(len(dp)):Item 0 needs to be initialized first. Item 0 can be evaluated forward
            dp[j]=nums[0] if j>=nums[0] else 0
        for i in range(1.len(nums)):
            for j in range(len(dp)-1,nums[i]-1, -1):
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])# Maximum value items that can fit into the current backpack capacity (the maximum integer sum that can be selected)
            if dp[-1]==c:# If the first I items fill the backpack of capacity C, select some integers, and the sum is half of the total elements
                return True
        return False

Copy the code

In fact, we can further optimize the 01 backpack problem under this condition, do not need to solve the actual value, just need to determine whether some items can be selected to fill the current backpack capacity.

class Solution:
    def canPartition(self, nums: List[int]) - >bool:        
        c=sum(nums)
        if c%2! =0:
            return False
        else:
            c//=2
        dp=[0 for _ in range(c+1)]
        for j in range(len(dp)):Item 0 needs to be initialized first. Item 0 can be evaluated forward
            dp[j]=True if j==nums[0] else False
        for i in range(1.len(nums)):
            for j in range(len(dp)-1,nums[i]-1, -1):
                dp[j]=dp[j] or dp[j-nums[i]]# Set the current state to True if either of the two integers can fill the current backpack capacity
            if dp[-1] :If dp[c] is True, it means that some integers can be selected, and the sum is half of the total element sum
                return True
        return False

Copy the code

Complete knapsack problem

The title

There are N items and a backpack of capacity V. The cost of putting in the ith item is C1i, and the value is Wi. An infinite number of items are available for each item. Figure out which items to pack into the backpack maximize the sum of values.

The basic idea

The full knapsack problem appears to be only slightly different from the 01 knapsack problem, except that the number of options for each item in the full knapsack problem is arbitrary.

It’s easy to think of a greedy way to prioritise the best value for money. However, there is still a problem, that is, although the same item can choose any number of pieces, it can still only be divided into units, that is to say, a single item can not be split, can not choose half, can only choose one more or one less. This creates a problem. It is often impossible to fill the entire backpack with the most cost-effective items. For example, the backpack space is 10, and the most cost-effective items take up 7 space.

Of course you want to fill it with the second best value item, and if that still doesn’t work, fill it with the third and fourth best value item.

It’s easy to take A counter example, say there are only two items: Item A: Value 5, volume 5, and Item B: Value 8: Volume 7, knapsack capacity of 10, item B obviously than items A high cost performance, so using A greedy algorithm will choose item B, at this point, the remaining space have been unable to hold A or B, so get the highest value of 8, and, in fact, into the two items can get A higher value of 10 A. So the greedy algorithm doesn’t work here.

From the perspective of each item, the strategies associated with it are no longer either take or not take, but take zero, take one, take two… Up to take [V /Ci] pieces and many other kinds. Based on the 01 knapsack problem, we can derive its dynamic programming transfer formula as follows:

It is not difficult to see that the 01 knapsack problem is a special case of the complete knapsack problem. Since 0 to [V /Ci] policies need to be traversed at this time, three levels of enumeration are required, and the total time complexity is

A simple and effective optimization is: if two items I and J meet Ci ≤ Cj and Wi≥Wj, item J can be directly removed without consideration. In any case, you can swap a j for a cheap I and get at least as good a solution. This is not the same as greedy algorithms, because not only do they need to be cost-effective, but they also need to be smaller in weight.

Converts to 01 knapsack problem

In fact, we can turn the complete backpack problem into a 01 backpack problem by splitting the different choices of an item into a number of 01 backpack items that can only choose 0 or 1.

Considering that item I can choose at most [V /Ci], item I can be converted into item [V /Ci] with the same cost and value.

Further optimization, we know that, considering the properties of binary numbers, any 1 number can be represented as a number of 2k combinations. So, we just need to split the item into log[V /Ci] pieces.

Spatial complexity optimization

Similar to the 01 knapsack problem, the spatial complexity of the complete knapsack problem can still be optimized by using state compression.

We can also use a similar method to reduce the spatial complexity to O(N), the only difference from the 01 knapsacks problem is that the DP table is filled forward instead of backward traversal.

This is because, in the 01 backpack problem, we can add at most 1 item of the same kind, so we can only add to the result of the previous I-1 item, reverse traversal to prevent the result from being overwritten. In the complete knapsack problem, we can add up to an infinite number of items. We can add on top of the results of the previous I items, and to use the results of the previous I items, we must traverse forward.

A sample

An example of a complete backpack question would be: interview question 08.11. Coins

Given an unlimited number of coins worth 25 cents, 10 cents, 5 cents and 1 cent, there are several ways to write code to calculate n cents. Obviously, this is a complete backpack problem, backpack size N, there are four items, we can think of them as the same value and weight. What we’re looking for here is not the maximum value, but the number of combinations that exactly fill the backpack.

class Solution:
    def waysToChange(self, n: int) - >int:
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        coins = [1.5.10.25]
        for coin in coins:
            for i in range(1, n+1):
                dp[i] += dp[i-coin] if i-coin>=0 else 0
        return dp[-1] % 1000000007

Copy the code

It should be noted that the conventional complete backpack problem can swap the position of the above two layers of circulation, but not in this problem, which will lead to repeated combinations, and traversing the currency value first can ensure that the value of the resulting combination of ascending order, so as not to repeat.