01Dynamic programming of knapsack problem

The basic idea of ​​dynamic programming:

Dynamic programming algorithms are usually used to solve problems with certain optimal properties, that is, what we usually call Said optimal substructure properties.

The dynamic programming algorithm is similar to the divide-and-conquer method. Its basic idea is to decompose the problem to be solved into several sub-problems, solve the sub-problems first, and then obtain the solution to the original problem from the solutions of these sub-problems. The biggest difference from the divide-and-conquer method is that for problems that are suitable for solving by dynamic programming, the sub-problems obtained after decomposition are often not independent of each other, that is, the solution of the next sub-stage is based on the solution of the previous sub-stage. Further solution.

If the divide-and-conquer method is used to solve this type of problem, the number of sub-problems obtained by decomposition will be too many, and some sub-problems will be recalculated many times. If we can save the answers to the solved sub-problems and find the obtained answers when needed, we can avoid a lot of repeated calculations and save time. We can use a table to record the answers to all solved subproblems. Regardless of whether the subproblem is used later, as long as it is calculated, its results are filled in the table.

Problem description:

Given N items and a backpack. The weight of item i is Wi, its value is Vi, and the capacity of the backpack is C. How should I choose the items to put in the backpack so that the total value of the items transferred to the backpack is maximized? ?

When selecting items, there are only two options for each item i, namely loading it into the backpack or not loading it into the backpack. You cannot load item i multiple times, nor can you load only part of the item. Therefore, this problem is called the 0-1 knapsack problem.

Problem analysis: Let V(i,j) represent that the capacity that can be loaded into the first i(1

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1) Formula shows: If the weight of the i-th item is greater than the capacity of the backpack, then the The maximum value obtained by item i is the same as the maximum value obtained by i-1 items before loading, that is, item i cannot be loaded into the backpack.

(2) Expression shows: If the weight of the i-th item is less than the capacity of the backpack, there will be two situations: (a) If the i-th item is not loaded into the backpack, then the value of the items in the backpack It is equivalent to the value obtained by putting the first i-1 items into a backpack with capacity j. (b) If the i-th item is put into the backpack, the value of the backpack item is equal to the value of the i-1th item in the backpack with capacity j-wi plus the value of the i-th item vi; Obviously, take The one with the greatest value is the optimal solution for loading the first i items into a backpack with a capacity of j.

Recommended tutorial: PHP tutorial

The above is the detailed content of 01Dynamic programming of knapsack problem. For more information, please follow other related articles on the PHP Chinese website!