View source for A Fast and Efficient Solution to the Backpack Problem

Written by [[Tels]]

==Abstract==
In 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.

==Preface==
Someone 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 [http://www.edm2.com/0601/backpack.zip example program]. However, they are marked as pseudocode, since they don't stand alone.

Abbreviations used in the article are:
;S: Size of the item (cost)
;V: Value of the item
;Q: Quality of the item (Q = S / V)
;M: Size of backpack (cost limit)
;Vc: Current value of items in backpack
;Mc: Space left in backpack at the moment
;Vb: Best value (solution) we ever found
;Mb: How much space did the best solution take? (Mb < M)

==General Considerations==
When 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:
<code>
   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;
   }
</code>
''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 Quality==
Every 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 / V
It 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 of the backpack solutions that are produced by the routine above. The best backpacks are now emitted first.

==Finding the optimal solution fast==
We 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 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:
<code>
   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 1997
</code>
''Figure 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:
<code>
   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 1997
</code>
''Figure 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:
<code>
   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 1997
</code>
''Figure 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:
<code>
   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 1997
</code>
''Figure 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 faster==
One 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.
<code>
   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 1997
</code>
''Figure 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 best==
Of 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.

==Alterations==
One useful alteration is to have a limit of how often every item can be used. For instance, when you fill a 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 many 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 simply convert the function to a non-recursive one.

The following code will construct such a constellation:
<code>
   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;
</code>
Here is the output of the program:
<code>
   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
</code>

==Conclusion==
You can download a sample program developed with Visual Age C++ for OS/2 [//www.edm2.com/0601/backpack.zip 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!

[[Category:C++ Articles]]