Multiple knapsack problem
Contents
1.problem introduction
2.algorithm introduction
3.Preliminary analysis
4.Pseudo code
5.Verification
6.Reference
problem introduction
The knapsack problem
Assume that you have a set of items, each with a (positive) weight and a (positive) value, and a knapsack (or bag) with a limited weight capacity. The problem is to choose (to include in the knapsack) items so that the weight capacity of the knapsack is not violated and the value of the chosen items are as high as possible.Mathematically, the problem can be formulated in the following way. We let I = {1, . . . , n} be an index set over the n items, where item i ∈ I have a value pi > 0 and a weight wi > 0, and we let W > 0 denote the weight capacity of the knapsack. For item i ∈ I, the binary decision variable xi is used to determine whether to include item i in the knapsack: xi = 1 if the item is chosen, and xi = 0 if it is not chosen.The objective function of the problem is to maximize the utility of the chosen items, i.e.,
All valid solutions to the problem should fulfill the weight constraint
and the values of the decision variables are restricted by the constraint set xi ∈ {0, 1} ∀i ∈ I.
The multiple knapsack problem
The multiple knapsack problem is an extension to the standard knapsack prob�lem in that it considers choosing items to include in m knapsacks (the standard knapsack problem considers only one knapsack).
Mathematically, the multiple knapsack problem can be formulated as follows.We let I = {1, . . . , n} be an index set over the n items, where item i ∈ I have a value pi > 0 and a weight wi > 0. In addition, we let J = {1, . . . , m} be an index set over the m knapsacks, where Wj > 0 denotes the weight capacity of knapsack j ∈ J. For item i ∈ I and knapsack j ∈ J, we let the binary decision variable xij determine whether to include item i in knapsack j: xij = 1 if item i is included in knapsack j, otherwise xij = 0.The objective function of the problem is to maximize the utility of the chosen items, i.e.,
For each of the knapsacks, the solution space is restricted by a weight capacity constraint, which states that the total weight of the selected items for that knapsack is not allowed to exceed the weight capacity of the knapsack. This is modeled by the following constraint set (one constraint for each of the m knapsacks):
In addition, it needs to be explicitly modeled that an item is not allowed to be included in more than one of the knapsacks. This is modeled by the following constraint set (one constraint for each of the n items):
Finally, the values of the decision variables are restricted by the constraint set xij ∈ {0, 1}, i ∈ I, j ∈ J
algorithm introduction
greedy algorithm
Greedy algorithms are simple and straightforward. They are shortsighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Many problems cannot be solved correctly by greedy approach. Greedy algorithms are used to solve optimization problems
-from Greedy Introduction(find more in reference)
Specifics
In general, greedy algorithms have five components:
- A candidate set, from which a solution is created
- A selection function, which chooses the best candidate to be added to the solution
- A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
- An objective function, which assigns a value to a solution, or a partial solution, and
- A solution function, which will indicate when we have discovered a complete solution
Shortcomings
We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage, and may reconsider the previous stage's algorithmic path to solution.For many other problems, greedy algorithms fail to produce the optimal solution, and may even produce the unique worst possible solution.
Preliminary analysis
If the items are already sorted into decreasing order of vi / wi, then the while-loop takes a time in O(n);
Therefore, the total time including the sort is in O(n log n).
If we keep the items in heap with largest vi/wi at the root. Then
- creating the heap takes O(n) time
- while-loop now takes O(log n) time (since heap property must be restored after the removal of root)
Although this data structure does not alter the worst-case, it may be faster if only a small number of items are need to fill the knapsack.One variant of the multiple knapsack problem is when order of items are sorted by increasing weight is the same as their order when sorted by decreasing value.The optimal solution to this problem is to sort by the value of the item in decreasing order. Then pick up the most valuable item which also has a least weight. First, if its weight is less than the total weight that can be carried. Then deduct the total weight that can be carried by the weight of the item just pick. The second item to pick is the most valuable item among those remaining. Keep follow the same strategy until we cannot carry more item (due to weight).
Pseudo code
Greedy-fractional-knapsack (w, v, W)
FOR i =1 to n
do x[i] =0
weight = 0
while weight < W
do i = best remaining item
IF weight + w[i] ≤ W
then x[i] = 1
weight = weight + w[i]
else
x[i] = (w - weight) / w[i]
weight = W
return x
for find the best remaining item , first i use merge sort to sort the element by values/weight
MERGE (A, p, q, r )
1. n1 ← q − p + 1
2. n2 ← r − q
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4. FOR i ← 1 TO n1
5. DO L[i] ← A[p + i − 1]
6. FOR j ← 1 TO n2
7. DO R[j] ← A[q + j ]
8. L[n1 + 1] ← ∞
9. R[n2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. FOR k ← p TO r
13. DO IF L[i ] ≤ R[ j]
14. THEN A[k] ← L[i]
15. i ← i + 1
16. ELSE A[k] ← R[j]
17. j ← j + 1
First recursive array elements, then do the merge sort.
function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length of m ≤ 1 then
return m
// Recursive case. First, divide the list into equal-sized sublists
// consisting of the first half and second half of the list.
// This assumes lists start at index 0.
var left := empty list
var right := empty list
for each x with index i in m do
if i < (length of m)/2 then
add x to left
else
add x to right
// Recursively sort both sublists.
left := merge_sort(left)
right := merge_sort(right)
// Then merge the now-sorted sublists.
return merge(left, right)
function merge(left, right)
var result := empty list
while left is not empty and right is not empty do
if first(left) ≤ first(right) then
append first(left) to result
left := rest(left)
else
append first(right) to result
right := rest(right)
// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
while left is not empty do
append first(left) to result
left := rest(left)
while right is not empty do
append first(right) to result
right := rest(right)
return result
introduce the functions used later
//use the item's value
void printList(Item[] arr)
//recurrence
void mergeSort(Item [] arr,int left,int right)
//mergesort
void merge(Item[] arr,int left,int middle,int right)
//sort knapsacks for possible exchanges
void sortKnap(Knapsack [] knapsackList, int left, int right)
//the item
Item(int number,float value, float weight)
//getvalue of item
float getValue()
//getweight of item
float getWeight()
//getknapsack
int getBag()
//getnumber
int getNumber()
//getCostperformance
float getCostPerformance()
//the kanpsack
Knapsack(float capacity,int number)
//try is full or not
Knapsack(Knapsack nap)
//getvalue of knapsack
float getValue()
//getweight of knapsack
float getWeight()
//return capacity
float capacity()
//capacity - getWeight()
float restCapacity()
//add item to knapsack
void addItem(Item i)
//remove item from knapsack
removeItem(Item i)
//get the number of item
int getItemNumber()
//get the information of item
String getItems()
The number, weight and value of items as well as the number and value of knapsacks are defined by the user
Scanner sc = new Scanner(System.in);
System.out.println("请输入物品的数量：");
int numberOfItems = sc.nextInt();
Item[] itemList = new Item[numberOfItems];
float valueOfItem = 0;
float weightOfItem = 0;
for(int i = 0; i<numberOfItems; i++) {
System.out.println("请输入物品"+String.valueOf(i+1)+"的价值:");
valueOfItem = sc.nextFloat();
System.out.println("请输入物品"+String.valueOf(i+1)+"的重量：");
weightOfItem = sc.nextFloat();
itemList[i] = new Item(i+1,valueOfItem,weightOfItem);
}
System.out.println("请输入背包数量: ");
int numberOfKnapsacks = sc.nextInt();
Knapsack[] knapsackList = new Knapsack[numberOfKnapsacks];
Knapsack[] firstKnapList = new Knapsack[numberOfKnapsacks];
float capacityOfKnapsack = 0;
for(int i = 0; i<numberOfKnapsacks; i++) {
System.out.println("请输入背包"+String.valueOf(i+1)+"的容量:");
capacityOfKnapsack = sc.nextFloat();
knapsackList[i] = new Knapsack(capacityOfKnapsack,i+1);
firstKnapList[i] = knapsackList[i];
}
Outputs the list of items before and after sorting，sort in descending order according to the cost performance of the items, and sort in ascending order the remaining space of the backpack
System.out.println("进行排序的物品列表:");
printList(itemList);
mergeSort(itemList,0,numberOfItems-1);
System.out.println("排序后的物品列表:");
printList(itemList);
sortKnap(knapsackList,0,numberOfKnapsacks-1);
The greedy algorithm main function corresponding to the above
for(int i = 0; i<numberOfItems; i++) {
for(int j = 0; j<numberOfKnapsacks; j++) {
if(knapsackList[j].restCapacity() >= itemList[i].getWeight()) {
knapsackList[j].addItem(itemList[i]);
break;
}
sortKnap(knapsackList,0,numberOfKnapsacks-1);
}
}
get the total value of all knapsacks
public static float getTotalValue(Knapsack[] knap) {
float sum = 0;
for(int i = 0; i<knap.length; i++) {
sum += knap[i].getValue();
}
return sum;
}
Output Result ( Greedy Algorithm )
System.out.println("经过贪婪算法后结果：");
for(int i = 0; i<numberOfKnapsacks; i++) {
totalValue += firstKnapList[i].getValue();
System.out.println("背包 "+ String.valueOf(firstKnapList[i].getNumber())+": "+firstKnapList[i].getItems()+"重量: "+String.valueOf(firstKnapList[i].getWeight())+" 价值: "+String.valueOf(firstKnapList[i].getValue()));
}
System.out.println("背包总价值: "+String.valueOf(totalValue));
Next is the neighborhood search algorithm,Taking the result of greedy algorithm as the initial value,Moving some item from one knapsack to another knapsack，Moving some other item away from knapsack (in order to make room for item i ，In the obtained solution, i is not included in any of the knapsacks.Moving some other item , which is not included in any knapsack in the current solution, into knapsack m′.
Knapsack[] newKnapList = new Knapsack[knapsackList.length];
Knapsack[] betterKnapList = new Knapsack[knapsackList.length];
boolean end = false;
while(!end) {
end = true;
for(int m = 0;m<knapsackList.length;m++) {
betterKnapList[m] = new Knapsack(knapsackList[m]);
}
for(int i = 0;i<knapsackList.length;i++) {
for(int j = 0;j<knapsackList[i].getItemNumber();j++) {
for(int m = 0;m<knapsackList.length;m++) {
newKnapList[m] = new Knapsack(knapsackList[m]);
}
newKnapList[i].removeItem(newKnapList[i].items.elementAt(j));
if(getTotalValue(newKnapList) > getTotalValue(betterKnapList)) {
end = false;
for(int m = 0;m<newKnapList.length;m++) {
betterKnapList[m] = new Knapsack(newKnapList[m]);
}
}
}
}
Then move the possible item for a better solution(if its exist).
for(int i = 0;i<knapsackList.length;i++) {
for(int j = 0;j<knapsackList[i].getItemNumber();j++) {
for(int m = 0;m<knapsackList.length;m++) {
newKnapList[m] = new Knapsack(knapsackList[m]);
}
for(int m = 0;m<newKnapList.length;m++) {
if(m == i) {
continue;
} else if(newKnapList[m].restCapacity()>= newKnapList[i].items.elementAt(j).getWeight()){
newKnapList[i].removeItem(newKnapList[i].items.elementAt(j));
newKnapList[m].addItem(newKnapList[i].items.elementAt(j));
if(getTotalValue(newKnapList) > getTotalValue(betterKnapList)) {
end = false;
for(int k = 0;m<newKnapList.length;k++) {
betterKnapList[k] = new Knapsack(newKnapList[k]);
}
}
} else {
continue;
}
}
}
}
add the item to the knapsack
for(int i = 0;i<itemList.length;i++) {
for(int m = 0;m<knapsackList.length;m++) {
newKnapList[m] = new Knapsack(knapsackList[m]);
}
if(itemList[i].getBag() != 0) {
continue;
} else {
for(int j = 0;j<knapsackList.length;j++) {
if(knapsackList[j].restCapacity() >= itemList[i].getWeight()) {
if(getTotalValue(newKnapList) > getTotalValue(betterKnapList)) {
end = false;
for(int m = 0;m<newKnapList.length;m++) {
betterKnapList[m] = new Knapsack(newKnapList[m]);
}
}
}
}
}
}
exchange the item if its necessary and output the result after neighborhood search algorithm
for(int i = 0;i<itemList.length;i++) {
for(int m = 0;m<knapsackList.length;m++) {
newKnapList[m] = new Knapsack(knapsackList[m]);
}
if(itemList[i].getBag() != 0) {
continue;
} else {
for(int j = 0;j<knapsackList.length;j++) {
for(int k = 0;k<knapsackList[j].items.size();k++) {
if(knapsackList[j].restCapacity()+knapsackList[j].items.elementAt(k).getWeight() >= itemList[i].getWeight()) {
newKnapList[j].removeItem(newKnapList[j].items.elementAt(k));
newKnapList[j].addItem(itemList[i]);
if(getTotalValue(newKnapList) > getTotalValue(betterKnapList)) {
end = false;
for(int m = 0;m<newKnapList.length;m++) {
betterKnapList[m] = new Knapsack(newKnapList[m]);
}
}
}
}
}
}
}
for(int m = 0;m<knapsackList.length;m++) {
knapsackList[m] = new Knapsack(betterKnapList[m]);
}
System.out.println("经过邻域搜索后结果:");
totalValue = 0;
for(int i = 0; i<numberOfKnapsacks; i++) {
totalValue += knapsackList[i].getValue();
System.out.println("背包 "+ String.valueOf(knapsackList[i].getNumber())+": "+knapsackList[i].getItems()+"重量: "+String.valueOf(knapsackList[i].getWeight())+" 价值: "+String.valueOf(knapsackList[i].getValue()));
}
System.out.println("背包总价值: "+String.valueOf(totalValue));
}
}
in some of cases，the result doesn‘t change ， and when some items have a high cost performance with also a high weight ， it might occupy the others‘ room whose cost performance are not as high as it but the total value are more than it ，and the rest space is not enough for their all in but both the high cost performance thing and the other can respectively into the knapsack ， in this situation the neighborhood research algorithm will have a better performance than greedy algorithm.
Verification
Its need to verify the choice property and optimal substructure property. It consist of two steps. First, prove that there exists an optimal solution begins with the greedy choice given above. The second part prove that if A is an optimal solution to the original problem S, then A - a is also an optimal solution to the problem S - s where a is the item thief picked as in the greedy choice and S - s is the subproblem after the first greedy choice has been made. The second part is easy to prove since the more valuable items have less weight.
Note that if v' / w', is not it can replace any other because w' < w, but it increases the value because v' > v.
Let the ratio v'/w' is maximal. This supposition implies that v'/w' ≥ v/w for any pair (v, w), so v'v / w > v for any (v, w). Now Suppose a solution does not contain the full w` weight of the best ratio. Then by replacing an amount of any other w with more w' will improve the value.
