Parallel Environment0-1Knapsack Problem Solving Strategy

In this thesis, the0-1knapsack problem-solving strategy theory. Papers in the pipeline technique and0-1knapsack problem based on theoretical studies, the pipeline of technology into items to be placed in bags in the preparatory work, with "greedy algorithm"thinking to solve the0-1knapsack problem.0-1knapsack problem on a large scale in order to effectively solve.0-1knapsack problem (Knapsack Problem, referred to as KP) is a classical combinatorial optimization problems, has broad application background. Many of the problems in life can be used to describe the knapsack problem, such as resource allocation, storage load, capital budget, storage allocation and project selection and so on knapsack problem can be modeled, and it is often used for other combinatorial optimization problems of a complex sub-problems. But when the scale is too large knapsack problem, if desired optimal solution is extremely difficult, to carry out large-scale studies0-1knapsack problem is significant.The traditional method of solving knapsack problem can be divided into two categories: exact algorithms (such as dynamic programming, branch and bound, backtracking, etc.) and approximate algorithms (eg greedy algorithm). Because the time complexity of exact algorithms is exponential growth, so gradually from the sixties made a number of approximation algorithms.In addition, pipelining is widely used in micro-processing chip, a key technology, his instructions to the CPU inside the modalities for the implementation of the parallel operations in space. The assembly line technology into the preparation phase of the0-1knapsack problem, knapsack problem will have some improving overall efficiency. After reading a lot of foreign literature, based on the0-1knapsack problem is proposed a new solution strategy. This paper introduces the concept of parallel machines, pipeline technology, and common thinking and problem solving0-1knapsack their respective performance is analyzed. In the greedy algorithm, inspired by ideas, combined with the characteristics of0-1knapsack problem, we propose a improvement measures to achieve in large-scale environment, the case of a large amount of data to improve the search speed of0-1knapsack problem of reconciliation quality. This paper from the initial data entry, analysis, calculation, all aspects of starting at the overall performance improvement in all aspects.