In the 0/1 backpack problem, the backpack of C is required to be loaded. The items loaded into the backpack are selected from the n items, and the weight of each item I is Wi, value is PI. For feasible backpack loading, the total weight of the items in the backpack cannot exceed the capacity of the backpack, and the best load is the highest value of the loaded item, namely n? I = 1pi xi acquired the maximum. The constraint conditions are n? I = 1 Wi ≤ C and XI? [0, 1] (1 ≤ i ≤ N).
In this expression, the value of XT is required. Xi = 1 indicates that the item I is loaded into the backpack, and Xi = 0 indicates that the item i does not load the backpack. 0/1 Backpack problem is a generalized freight box load problem, that is, the value obtained by each cargo box. The form of the container load problem is in the form of a backpack problem: the ship acts as a backpack, and the container is an item that can be loaded into the backpack. Example 1-8 You got the first place in the grocery store, the prize is a free groceries. There are N different goods in the store. Rule stipulates up to one more in each car, the capacity of the car is c, and the item I takes up the space of Wi, value is PI. Your goal is to maximize the value loaded in the car. Of course, the goods cannot exceed the capacity of the car, and the same item must not take multiple pieces. This problem can be modeled in the 0/1 backpack problem, and the car corresponds to the backpack, and the goods correspond to the item.
0/1 Backpack problem has several greedy strategies, each of which uses a multi-step process to complete the loading of the backpack. Use greed guidelines to load backpacks in each step. A greedy criterion is: from the remaining items, select the most value of the value of the backpack, using this rule, the most value of the value is first loaded (assuming enough capacity), then the next value is the largest This continues. This strategy cannot guarantee the optimal solution. For example, consider N = 2, W = [100, 10, 10], p = [20, 15, 15], c = 1 0 5. When utilizing the value greed, the solution is obtained as x = [1, 0, 0], and the total value of this solution is 2 0. The optimal solution is [0, 1, 1], with a total value of 3 0.
Another solution is that the weight greed is: select the minimal weight of the weight of the backpack from the remaining items. Although this rule can produce the optimal solution for the previous example, it is not necessarily the optimal solution if in general. Consider N = 2, W = [10, 20], P = [5, 100], C = 2 5. When using a weight greedy policy, the solution is obtained as X = [1, 0], which is worse than the optimal solution [0, 1].
You can also use another plan, value density PI / Wi greedy algorithm, this selection criterion is: from the residual item
This strategy cannot guarantee the optimal solution. The optimal solution at the time of C = 30 when this policy is analyzed.
We don't have to guarantee the best solution and frustration because of several greedy algorithms, 0/1 backpack issues are N p-complex problems. For such issues, it may not be possible to find an algorithm with a polynomial time. Although the order is not guaranteed to be optimalized in the order of PI / Wi-in-order (increasing), it is not guaranteed, but it is an intuitive solution. We hope it is a good heuristic algorithm, and most of the time can closely close the final algorithm. In 6 0 0 randomly generated backpack problems, this heuristic greedy algorithm is used to solve 2 3 9 questions with the optimal solution. There are 5 8 3 examples of the optimal solution of 1 0%, and all 6 0 0 answers are within 2 5% of the optimal solution. This algorithm can achieve such good performance in the O (NL O GN) time. We might ask if there is an X (x <1 0 0), so that the result of the greedy inspiration method is within X% of the optimal value. the answer is negative. In order to illustrate this, consideration of N = 2, W = [1, Y], P = [1 0, 9Y], and C = Y. The greedy algorithm result is x = [1,0], and the value of this solution is 1 zero. For Y≥1 0/9, the value of the optimal solution is 9 y. Therefore, the value of the greedy algorithm and the optimal solution is the proportion of the optimal solution ((9y - 1 0) / 9y * 1 0 0)%, for large Y, this value is nearly 1 0%. However, a greedy heuristic method can be established to provide a solution, and the difference between the result of the resolution is within X% (x <100) of the optimum value of the value of the optimal value. First put the up to K item items into the backpack, if the weight of this k piece is greater than C, give it. Otherwise, the remaining capacity is used to consider loading the remaining items in order of PI / Wi decreasing. The optimal solution is obtained by considering the most possible subsets of the solution generated by the heuristic method. Example 13-9 Consider N = 4, W = [2, 4, 6, 7], P = [6, 10, 12, 13], C = 11. When k = 0, the backpack is loaded in order of the item value density, first put the item 1 into the backpack, then the article 2, the remaining capacity of the backpack is 5 units, and the remaining items do not have a suitable, so Solution to x = [1, 1, 0, 0]. This solution is worth 1 6.
Now consider the greedy inspiration in k = 1. The initial subset is {1}, {2}, {3}, {4}. The subset {1}, {2} produces the same result as K = 0, considering subset {3}, and set X3 to 1. There are also 5 units left at this time, consider how to use these 5 units in the value of the value density. First consider the item 1, it is suitable, so the x1 is 1, only 3 unit capacity remains, and the remaining items are not capable of adding the items in the backpack. The result is X = [1, 0, 1, 0] by subset {3}, and the value is 1 8. If the resulting solution is obtained from the subset {4}, the value is 1 9. The optimal solution obtained when considering the subset size of 0 and 1 is [1, 0, 0, 1]. This solution is obtained by K = 1 greedy heuristic algorithm.
If K = 2, in addition to the subset of K <2, it is necessary to consider subset {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} and { 3, 4}. First, starting from the last subset, it is not feasible, so abandon it, the rest of the subset is obtained from the following results, respectively: [1, 1, 0, 0], [1, 0, 1, 0] [1, 0, 0, 1], [0, 1, 1, 0] and [0, 1, 0, 1], the last value of 2 3 in these results, its value ratio K = 0 and K = 1 The solution is high, this answer is the result of the heuristic method. This modified greedy inspiration method is called the K-Order optimization method (K - O P I m a L). That is, if K component items are removed from the answer, and the results obtained will not be better than the original, and the value obtained in this manner is in the optimum value (1 0 0 / (k 1)))%. When k = 1, the final result is guaranteed to be within 5 0% of the optimum value; when K = 2, then within 3 3. 3 3%, etc., the execution time of this heuristic method increases with K In addition, the number of subsets required to test is O (NK), and each subset is required to be o (n), so when k> 0 is time overhead to O (NK 1). The actual performance is much better. Reprinted from Shada Studio
