A Fast and Efficient Solution to the Backpack ProblemWritten by Tels |
AbstractIn a backpack problem, you have different items and a limit. The items have a certain cost (e.g. size) and a certain value (e.g. resale value) associated with them. The limit is a cost-limit (e.g. size limit). The goal is to find that combination of items that is below the given cost-limit but gives the best value. In this article you will find some solutions which will settle this problem once and for all. PrefaceSomeone suggested Dynamic Programming to solve this problem (Sedgewick). But this is not only slow, it can't handle floating point values. Someone suggested Branch & Bound to solve this (Domschke?). Well, it works, but it's surely an overkill for such a simple problem. :-) However, when you limit the count of each item that is available, the problem very fast becomes a very hard one to solve. For instance, limiting the item count to 1 for each item makes the problem one of the hardest problems, and it is believed that there is no general solution to this problem. Code examples are C code ripped from the example program. However, they are marked as pseudo code, since they don't stand alone. Abbreviations used in the article are:
General ConsiderationsWhen we search for a solution, we should first try to write code that gives us every solution. We stuff our items in a single-linked list and pass a pointer to that list to our fill function. Here is a code snippet int fillBackpack (item* pItem) { double lTry; item* next; if (Mc == 0) { // we can't fit any more items inside // backpack: must be full // even current item won't fit! return (printBackpack()); } next = pItem->next; lTry = floor((double)Mc / pItem->size); if (next == NULL) { // end of items reached, backpack can't get fuller // fill with maximum count and stop there pItem->used = lTry + 1; Mc = Mc - (double)lTry * pItem->size; Mv = Mv + (double)lTry * pItem->value; printBackpack(); pItem->used = 0; Mc = Mc + (double)lTry * pItem->size; Mv = Mv - (double)lTry * pItem->value; return 1; } for ( ; lTry >= 0; lTry--) { // insert current item lTry times into backpack pItem->used = lTry + 1; // and now take next item and free // space in backpack that is left Mc = Mc - (double)lTry * pItem->size; Mv = Mv + (double)lTry * pItem->value; fillBackpack (next); // reset values pItem->used = 0; Mc = Mc + (double)lTry * pItem->size; Mv = Mv - (double)lTry * pItem->value; } return 0; }Figure 1: Code snippet. This code will enumerate all possible backpack combinations. It is, however, very slow since it does a tremendous amount of work. The QualityEvery item has a certain size and a certain value. This means that every item gives us a certain value per one size units it needs. We will call this the Quality Q, whereas: Q = S / VIt is pretty obvious that only items with a high quality can fill our backpack for the best solution. (Which thief would take glass if he could get diamonds?) So we try to fill in the best items first. To accomplish this, we have to sort our list of items before we start to fill the backpack. This can be done with one of the best sorting algorithms available. For demonstration purposes, we just add items to a single linked list in sorted order. This sorting will change the order the backpack solutions that are produced by the routine above. The best backpacks are now emitted first. Finding the optimal solution fastWe will find the optimal solution with this approach, since we find all solutions. But we don't need other solutions, so we add some abort conditions to the recurse algorithm above. The first thing we want to change is the line: if (Mc == 0)to the line: if (Mc == dSmallestItemSize)So our algorithm doesn't have to test dozens of combinations when even a single single item won't fit in the backpack. The value of dSmallestItem can be calculated by a simple loop over all items in O(N) time. The next, and crucial, condition is the maximum possible backpack we can find at any time. Whenever we find a solution, we check to see if it is better than any solution so far, and if yes, remember it. On entry to the fillbackpack routine we test what value our backpack would get if we would fill it with the current item up to the brim. Since our items are sorted by quality, the current item can't possibly fill the space left better than the item before. Even leaving out the current item, and using one of the items after the current can't do this, since the quality drops down the list. The maximum possible value of the backpack is then compared to the already best solution found so far. If it is lower or equal, we can stop, we won't get a better solution in this branch. Since we find the best solutions at the very start, this cuts down the work very effectively. Here are some benchmark results: BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Size Value Quality Count 23.0000 71.0000 3.0870 0 32.0000 63.0000 1.9688 0 54.0000 99.0000 1.8333 0 59.0000 76.0000 1.2881 0 41.0000 52.0000 1.2683 0 87.0000 94.0000 1.0805 0 79.0000 77.0000 0.9747 0 54.0000 31.0000 0.5741 0 83.0000 21.0000 0.2530 0 39.0000 9.0000 0.2308 0 Starting... Backpack of size 200.0000 (filled: 184.0000, value 568.0000): Size Value Quality Used 23.0000 71.0000 3.0870 8 Backpacks tried: 1 Calls to fillBackPack(): 10 Best: (Mstop: 200.00) (Sorting ON, Best_only ON, Early_out OFF) Size: 200.00 Filled: 184.00 Value: 568.00 Items: 1 Done. (Start: Tue Oct 21 15:51:29 1997, after sort: Tue Oct 21 15:51:29 1997 Stop: Tue Oct 21 15:51:29 1997Figure 2: Benchmark 1 of example 1, best only. As you can see, with only 10 calls to fillBackPack() we found the optimal solution. Here is the output if we try all solutions: BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Size Value Quality Count 23.0000 71.0000 3.0870 0 32.0000 63.0000 1.9688 0 54.0000 99.0000 1.8333 0 59.0000 76.0000 1.2881 0 41.0000 52.0000 1.2683 0 87.0000 94.0000 1.0805 0 79.0000 77.0000 0.9747 0 54.0000 31.0000 0.5741 0 83.0000 21.0000 0.2530 0 39.0000 9.0000 0.2308 0 Starting... Backpack of size 200.0000 (filled: 184.0000, value 568.0000): Size Value Quality Used 23.0000 71.0000 3.0870 8 Backpacks tried: 1 Calls to fillBackPack(): 10 Best: (Mstop: 200.00) (Sorting ON, Best_only OFF, Early_out OFF) Size: 200.00 Filled: 184.00 Value: 568.00 Items: 1 Done. (Start: Tue Oct 21 15:53:39 1997, after sort: Tue Oct 21 15:53:39 1997 Stop: Tue Oct 21 15:53:39 1997Figure 3: Benchmark 2 of example 1 - all solutions. Since both versions were completed in a fraction of a second, let's try a little bit more. We add 1000 randomly generated items to our list and set the size of the backpack to 20000. The output will be: BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Warning: More than 12 items in list, printing only first 12. Size Value Quality Count 1.0000 100.0000 100.0000 0 1.0000 99.0000 99.0000 0 1.0000 85.0000 85.0000 0 1.0000 82.0000 82.0000 0 1.0000 76.0000 76.0000 0 1.0000 68.0000 68.0000 0 1.0000 48.0000 48.0000 0 1.0000 45.0000 45.0000 0 2.0000 89.0000 44.5000 0 2.0000 85.0000 42.5000 0 1.0000 42.0000 42.0000 0 2.0000 82.0000 41.0000 0 Starting... Backpack of size 20000.0000 (filled: 20000.0000, value 2000000.0000): Size Value Quality Used 1.0000 100.0000 100.0000 20000 Backpacks tried: 1 Calls to fillBackPack(): 20002 Best: (Mstop: 20000.00) (Sorting ON, Best_only ON, Early_out OFF) Size: 20000.00 Filled: 20000.00 Value: 2000000.00 Items: 1 Done. (Start: Tue Oct 21 15:56:27 1997, after sort: Tue Oct 21 15:56:27 1997 Stop: Tue Oct 21 15:56:27 1997Figure 4: Benchmark 1 of example 2 - best solution with bad items. As you notice, there is a big drop in quality from the first item to the second. When we use more elements, it gets even bigger. This is due to the fact that we evenly distributed the size and the value of the generated items, but not the quality. When the drop in quality is that much, the algorithm is very fast! We can fix this by distributing the size and quality, and calculating the value from these both characteristics. This will produce: BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Warning: More than 12 items in list, printing only first 12. Size Value Quality Count 8.1053 89.1560 10.9997 0 4.7523 52.2690 10.9988 0 1.0378 11.4093 10.9933 0 3.3707 37.0250 10.9844 0 5.6525 62.0469 10.9768 0 5.0693 55.5554 10.9591 0 2.8995 31.7323 10.9442 0 5.0770 55.4159 10.9152 0 8.2851 90.4228 10.9139 0 4.4620 48.6778 10.9094 0 2.6309 28.6999 10.9087 0 4.5215 49.1821 10.8773 0 Starting... Backpack of size 20000.0000 (filled: 19999.9743, value 219993.5867): Size Value Quality Used 8.1053 89.1560 10.9997 2467 1.0378 11.4093 10.9933 4 Backpacks tried: 1 Calls to fillBackPack(): 2475 Best: (Mstop: 20000.00) (Sorting ON, Best_only ON, Early_out OFF) Size: 20000.00 Filled: 19999.97 Value: 219993.59 Items: 3 Done. (Start: Tue Oct 21 15:59:27 1997, after sort: Tue Oct 21 15:59:27 1997 Stop: Tue Oct 21 15:59:27 1997Figure 5: Benchmark 2 of example 2 - best solution with better items. The time taken was only 1 second in both cases, though. Although the second example shows only very few calls to fillBackPack(), it had more work to do since it tested more backpacks. The first example had to struggle with the very small size of the best element compared to the backback size. When trying to enumerate all solutions, we fail: the algorithm will run several hours (days?) on a fast Pentium. Finding the solution even fasterOne problem with this algorithm is the stopping when we have found a backpack which we can't possible improve with items further down our list. In this case we stop, but the fillbackpack() routine a step above (that which called us) will reduce its lTry variable and then try again. But since the situation can get only worse (if the item before is better than the current) or at best remains unchanged (if previous item is equal to current item), there is not much sense in trying this. When we pack only one or two items in the backpack, this is not critical (even 2000000 million calls to fillbackpack() are very fast!). But when we have already a couple different items in our backpack, we try millions of combinations and do a lot of unnecessary calls. We can fix this by returning two for that special abort condition and test for two after return from fillBackPack(). The next problem with the algorithm is the sorting. For backpacks that are only filled with one item, it is not necessary to sort the entire list of items. We can just pick the best item, fill the backpack and be done. But how will we know when to do this? When there are more than two different items in the best solution, picking the best item takes for every item N/2 steps to find it, and this recurse! A quick test if we are done with only the best item, and if it fails we do the entire sorting and filling. If we have millions of items in a unsorted list, this will save us the sorting time. But for item counts < 10000 it will yield almost no performance difference on a standard PC. Note: The first optimization works only if the items are sorted by quality and size. Items with an equal quality have to be sorted by size, too. The smallest items have to be preferred over the larger items. It is easy to adapt the sorting algorithm to do that, but you have to change the findBestNextItem() algorithm to do the same! This is because larger items will leave a larger space in the backpack than smaller ones, since we can't split up items. BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Warning: More than 12 items in list, printing only first 12. Size Value Quality Count 8.1053 89.1560 10.9997 0 4.7523 52.2690 10.9988 0 1.0378 11.4093 10.9933 0 3.3707 37.0250 10.9844 0 5.6525 62.0469 10.9768 0 5.0693 55.5554 10.9591 0 2.8995 31.7323 10.9442 0 5.0770 55.4159 10.9152 0 8.2851 90.4228 10.9139 0 4.4620 48.6778 10.9094 0 2.6309 28.6999 10.9087 0 4.5215 49.1821 10.8773 0 Starting... Backpack of size 20000.0000 (filled: 19999.9743, value 219993.5867): Size Value Quality Used 8.1053 89.1560 10.9997 2467 1.0378 11.4093 10.9933 4 Backpacks tried: 1 Calls to fillBackPack(): 6 Deepest: 4 Best: (Mstop: 20000.00) (Sorting ON, Best_only ON, Early_out ON) Size: 20000.00 Filled: 19999.97 Value: 219993.59 Items: 3 Done. (Start: Tue Oct 21 16:04:16 1997, after sort: Tue Oct 21 16:04:16 1997 Stop: Tue Oct 21 16:04:16 1997Figure 6: Benchmark 3 of example 2 - with early out termination. As you can see, the early out technique reduces the calls to fillBackPack() dramatically! Finding not THE best solution, but NEARLY the bestOf course it is not necessary in every case to find the exact best solution. We can, for instance, limit the work our program does, when we stop it as soon as it has reached a certain backpack size. See Mmax in the source code for how to do this. AlterationsOne useful alteration is to have a limit of how often every item can be used. For instance, when you fill an transporter, you can only use items that are currently at hand or in your warehouse. It is easy to implement, just limit the lTry variable to how much items you have in reality. This will slow down the algorithm when there are fewer items than could be placed into the backpack. Another useful alteration could be the removal of the recursion. It is not a problem to compile an OS/2 program with a stack size of one MByte, but for large numbers of different items even this can't be enough. When we remove the recursion, we can emulate the stack on the heap, thus using a dynamically allocated memory. It is possible to construct item combinations, so that every different item is needed for the best solution! To remove the recursion, we should use the used variable of every item to store lTry in it directly. When lTry is thus no longer needed we can simple convert the function to an non-recursive one. The following code will construct such a constellation: M = 0; s=3; for (i=0; i<20; i++) { s= s*3; } q = 2000; for (i=0; i<20; i++) { M = M + s; addItem (itemlist, &N, s, s*q, 0); printf ("\r Adding: %i ", i); s = (s / 3); q -= 1; } M += 1;Here is the output of the program: BackPack v1.1 (c) Copyright by Tels 1997. All Rights Reserved. Warning: More than 12 items in list, printing only first 12. Size Value Quality Count 10460353203.0000 20920706406000.0000 2000.0000 0 3486784401.0000 6970082017599.0000 1999.0000 0 1162261467.0000 2322198411066.0000 1998.0000 0 387420489.0000 773678716533.0000 1997.0000 0 129140163.0000 257763765348.0000 1996.0000 0 43046721.0000 85878208395.0000 1995.0000 0 14348907.0000 28611720558.0000 1994.0000 0 4782969.0000 9532457217.0000 1993.0000 0 1594323.0000 3175891416.0000 1992.0000 0 531441.0000 1058099031.0000 1991.0000 0 177147.0000 352522530.0000 1990.0000 0 59049.0000 117448461.0000 1989.0000 0 Starting... Backpack of size 15690529801.0000 (filled: 15690529800.0000, value 31373214335190.0000): Size Value Quality Used 10460353203.0000 20920706406000.0000 2000.0000 1 3486784401.0000 6970082017599.0000 1999.0000 1 1162261467.0000 2322198411066.0000 1998.0000 1 387420489.0000 773678716533.0000 1997.0000 1 129140163.0000 257763765348.0000 1996.0000 1 43046721.0000 85878208395.0000 1995.0000 1 14348907.0000 28611720558.0000 1994.0000 1 4782969.0000 9532457217.0000 1993.0000 1 1594323.0000 3175891416.0000 1992.0000 1 531441.0000 1058099031.0000 1991.0000 1 177147.0000 352522530.0000 1990.0000 1 59049.0000 117448461.0000 1989.0000 1 19683.0000 39129804.0000 1988.0000 1 6561.0000 13036707.0000 1987.0000 1 2187.0000 4343382.0000 1986.0000 1 729.0000 1447065.0000 1985.0000 1 243.0000 482112.0000 1984.0000 1 81.0000 160623.0000 1983.0000 1 27.0000 53514.0000 1982.0000 1 9.0000 17829.0000 1981.0000 1 Backpacks tried: 1 Calls to fillBackPack(): 39 Deepest: 20 Best: (Mstop: 15690529801.00) (Sorting ON, Best_only ON, Early_out ON) Size: 15690529801.00 Filled: 15690529800.00 Value: 31373214335190.00 Items: 20 Done. (Start: Tue Oct 21 16:09:12 1997, after sort: Tue Oct 21 16:09:12 1997 Stop: Tue Oct 21 16:09:12 1997 ConclusionYou can download a sample program developed with Visual Age C++ for OS/2 here. The program should compile with few problems on other operating systems or compilers. If not, let us know. Please note that it is difficult to get the algorithm to spend some time, it is fast as hell even for LARGE test item counts ;-) Hope you had fun! |