Week 13 summary blog (week 15 of the school calendar) dynamic planning summary

• Iterative method

• Suppose first dp[0][0] Value , Make a round dp Get a new dp[0][0] Value . Repeat the above calculation with the new value , Until twice dp[0][0] The difference between the values of is small enough .

• Optimize

• The initial value is ans0, The new value is ans1, The actual answer is ans. From the results of the iterative method , When ans0 Than ans Big time ,ans1 Than ans0 Small ;ans0 Than ans Hours ,ans1 Than ans0 Big .

• Conform to the nature of dichotomy .

• Time complexity O(nS·log).

One ：01 knapsack

This is the basic knapsack problem , Characteristic is : There is only one item of each kind , Take , Or not .

use F[i,v] Before presentation i Put one item into a container with a capacity of v The maximum value that you can get from your backpack . Before i The capacity of items is v The schemes in the backpack can be divided into two categories : Don't select the second i And select the i Pieces of , Thus the state transition equation can be obtained :

F[i,v]=max{F[i-1,v], F[i-1,v-C[i]]+W[i]}

F[0, 0..V] = 0

        for i = 1 to N

                for v = C[i] to V

                        F[i,v] = max{F[i-1, v], F[i-1, v-C[i]] + W[i]}

The time and space complexity are O(N*V), Among them, the time complexity can no longer be optimized Changed , But the space complexity can be optimized to O(V)

F[0..V] = 0

        for i = 1 to N

                for v = V to C[i]

                        F[v] = max{F[v], F[v-C[i]] + W[i]}

v Perform the decreasing cycle guarantee calculation F[i,v] when , F[i-1,v-C[i]] No first i Items selected into , from And make sure you only choose one item

Two ： Complete knapsack problem

This question is very similar to 01 knapsack problem , The difference is that each item can take 0 Pieces of 、 take 1 Pieces of 、 take 2 Pieces of ……, Until ⌊V /C[i]⌋ Pieces, etc .

If you still follow the solution 01 The idea of backpacking , Make F[i,v] Before presentation i Put items into a container The quantity is v The maximum weight of the backpack , It is still possible to follow paragraph i Write the following state transition equation for the strategy of selecting or not selecting items :

F[i,v]=max{f[i-1,v-kC[i]]+kW[i]|0<=kC[I]<v}

  But the implementation complexity of this method is relatively high .

F[0..V] = 0

         for i = 1 to N

                for v = C[i] to V

                        F[v] = max(F(v), F[v-C[i]] + W[i])

3、 ... and ： Multiple backpack

（1） Binary optimization

（2） Monotonic queue optimization

I feel it is very difficult to see the dynamic planning problem , puff . Plus, I've been busy doing other things this week , A big mistake , I don't learn much by myself , Feeling of poverty . Next week we will find more time to learn algorithms .