Dynamic programming | 0-1 knapsack problem

1、 Problem analysis

Yes n The capacity of items and shopping carts , Each item weighs w[i], Value is v[i], The capacity of the shopping cart is W. Select several items and put them in the shopping cart , Maximize its value , It can be expressed as follows ：

The problem boils down to solving the constraint conditions , The solution vector that maximizes the objective function X = {x1,x2,…,xn}.

First, we analyze whether the problem has optimal substructure properties .

（1） Analyze the structural characteristics of the optimal solution

• Suppose until X = {x1,x2,…,xn} It's the original question {a1,a2,…,an} The best solution , Then the original problem becomes a sub problem after removing the first item {a2,a3…,an}, Pictured 4-89 Shown .

• The constraints and objective functions of the subproblem are as follows .

• We just need to prove ： X’ = {x2,x3,…,xn} It's the original question {a2,a3,…,an} The best solution , That is, the optimal substructure property is proved .

（2） Establish the recursive formula of the optimal value

use c[i][j] Before presentation i Put one item into a container with a capacity of j The maximum value you can get from your shopping cart .

• Don't put it in the second i Item ,xi = 0