Bin Packing Problem With Profit Maximization

In order to improve the packing profit,we consider the bin packing problem with profit maximization,which is a generalization of the multiple knapsack problem,and it is defined as follows.Given a set A={a1,a2,…,an}of items and a set B={b1,b2,…,bm}of bins,each item ai has a size w(ai)and a price p(ai),where i=1,2,…,n.and each bin bj has a capacity s(bj)and a cost c(bj),where j=1,2,…,m,we are asked to select some items to put into some bins,such that the sum of sizes of the items in each bin can not exceed the capacity of the bin.The objective is to maximize the net profit,i.e.(?),where B'is the set of used bins and T(B')is the set of items in all bins of B'.We provide a polynomial time heuristic algorithm to solve the bin packing problem with profit maximization,and its complexity is max{O(nm),O{nlogn)}.In addition,the algorithm is programmed by JAVA,and some experiments are presented by using this program on several examples.