The Research Of Hybrid Greedy Algorithm Based On Comprehensive Knapsack Problem

Knapsack problem is a NP complete combinatorial optimization problem.Problems can be described as,given a backpack and a set of items,each item has its own weight and value,in the backpack weight limit,by choosing some items,making the highest total value of the item.Knapsack problem often appears in the field of business,combinatorial mathematics,cryptography,etc.0-1 knapsack problem,rely on is based on the concept of knapsack problem extensions of NP complete problem,but with the increase of the complexity of the problem to be solved,the traditional 0-1knapsack problem and rely on can not describe complicated practical problems.This paper puts forward a 0-1 knapsack problem,dependency problem and MKP(Multi-dimensional Knapsack Problem)based on the theory of attach other limiting factors of complex integrated knapsack problem.Comprehensive knapsack problem can be described as,given a set of items,each item has its own weight and degree,degree obtained by the degree and the degree of additive.Items have shown a relationship between each other,such as items item0 depends on item1 and item2,item0 degree is 2,which assumes that exists to item0 item1 dependencies,in under the condition of only considering item1 a dependency,item0 into degree is 1,which also can be seen that degree is a one-way.Besides given a set of items,comprehensive knapsack problem is not like the traditional knapsack problem give only a backpack,but unknown number of backpack.The weight of each bag to hold values are the same,moreover each backpack into the degree and the degree is limited quantity.Backpack into the degree and the degree of dependence in pack all items into the degree and the degree of accumulation.Comprehensive solution can be described as the knapsack problem,in no morethan the weight of each bag and not in violation of the degree and the degree of limitation,use the least number of backpack,will all the items in a group of backpack.This paper studies the dependence on different weighted algorithm of greedy algorithm calculates the comprehensive the relative optimal solution of the knapsack problem by using different weighted algorithm to calculate the weighted factor sequence,in the case of the meet the local optimal solution,make successive greedy choice,in the form of iteration to get the final solution of the problem.Finally,according to the different weighting algorithm is analyzed,it is concluded that the ultimate solution to find a comprehensive knapsack problem of the optimal solution.