Recursion problem 1

[mikrom]

This is a tip to the recursion problem from C-thread

http://www.tek-tips.com/viewthread.cfm?qid=1512288&page=1

Given are packages, each with a given weight and a number of trucks with a max load capacity. The packages should be loaded on the trucks.
The problem should be solved recursivelly.

E.g we have this list of packages
packages = [5, 3, 8, 2, 1, 2, 3, 5, 2]
i.e.
1. package with weight 5
2. package with weight 3
..etc

and 3 trucks with the same max capacity=10

For Loading one truck I use recursive procedure:
1. I try to load first package from the list
2. and then I try to load the rest of packages.

For loading all packages on the 3 trucks:
1. load first truck
2. then load second truck
3. at end load last truck

Here is the program trucks.py

def truck(load, capacity, packages):
  """ 
     Parameters:
        load     = list of packages loaaded on the truck
        capacity = maximal possible weight of loading
        packages = plist of packages available
  """
  print "Calling: truck(%s, %s, %s)" % (load, capacity, packages)
  # compute load weight
  total_load=total(load)
  if packages != [] and total_load != capacity :
    # try to load first package to truck
    load.append(packages[0])
    # compute load weight
    total_load=total(load)
    if total_load > capacity:
      # remove last package from truck  
      load = load[:-1]      
    # try with the next package
    load=truck(load, capacity, packages[1:])
  # return list of packages loaded on the truck
  return load

def total(packages):
  sum = 0
  for package in packages:
    sum += package
  # return value
  return sum

def list_difference(list, sublist):
  difference_list=list
  for element in sublist:
    if element in list:
      difference_list.remove(element)
  return difference_list


def main():
  capacity = 10
  packages = [5, 3, 8, 2, 1, 2, 3, 5, 2]

  # 1.Truck
  print "Original packages = %s\n" % packages
  print "Loading packages on 1.Truck:"
  load=truck([], capacity, packages)
  print "1.Truck loaded with packages %s => total weight=%d\n"\
      % (load, total(load))

  # 2.Truck
  packages = list_difference(packages, load)
  print "Remaining packages = %s" % packages
  print "Now loading remaining packages on 2.Truck:"
  load=truck([], capacity, packages)
  print "2.Truck loaded with packages %s => total weight=%d\n"\
      % (load, total(load))

  # 3.Truck
  packages = list_difference(packages, load)
  print "Remaining packages = %s" % packages
  print "Now loading remaining packages on 3.Truck:" % packages
  load=truck([], capacity, packages)
  print "3.Truck loaded with packages %s => total weight=%d\n"\
      % (load, total(load))

  # Packages remaining at end
  packages = list_difference(packages, load)
  print "Remaining packages = %s" % packages

if __name__ == "__main__":
  main()

The output demonstrates how it works

D:\>trucks.py
Original packages = [5, 3, 8, 2, 1, 2, 3, 5, 2]

Loading packages on 1.Truck:
Calling: truck([], 10, [5, 3, 8, 2, 1, 2, 3, 5, 2])
Calling: truck([5], 10, [3, 8, 2, 1, 2, 3, 5, 2])
Calling: truck([5, 3], 10, [8, 2, 1, 2, 3, 5, 2])
Calling: truck([5, 3], 10, [2, 1, 2, 3, 5, 2])
Calling: truck([5, 3, 2], 10, [1, 2, 3, 5, 2])
1.Truck loaded with packages [5, 3, 2] => total weight=10

Remaining packages = [8, 1, 2, 3, 5, 2]
Now loading remaining packages on 2.Truck:
Calling: truck([], 10, [8, 1, 2, 3, 5, 2])
Calling: truck([8], 10, [1, 2, 3, 5, 2])
Calling: truck([8, 1], 10, [2, 3, 5, 2])
Calling: truck([8, 1], 10, [3, 5, 2])
Calling: truck([8, 1], 10, [5, 2])
Calling: truck([8, 1], 10, [2])
Calling: truck([8, 1], 10, [])
2.Truck loaded with packages [8, 1] => total weight=9

Remaining packages = [2, 3, 5, 2]
Now loading remaining packages on 3.Truck:
Calling: truck([], 10, [2, 3, 5, 2])
Calling: truck([2], 10, [3, 5, 2])
Calling: truck([2, 3], 10, [5, 2])
Calling: truck([2, 3, 5], 10, [2])
3.Truck loaded with packages [2, 3, 5] => total weight=10

Remaining packages = [2]

 

[Bong]

Very nice.
Might it be more efficient to sort the list first (packages.sort() and possibly followed by packages.reverse())?

_________________
Bob Rashkin

 

[mikrom]

Hi Bong,

If you use in main()

  ...
  packages = [5, 3, 8, 2, 1, 2, 3, 5, 2]
  packages.sort()
  ...

Then the result will be

Original packages = [1, 2, 2, 2, 3, 3, 5, 5, 8]

Loading packages on 1.Truck:
Calling: truck([], 10, [1, 2, 2, 2, 3, 3, 5, 5, 8])
Calling: truck([1], 10, [2, 2, 2, 3, 3, 5, 5, 8])
Calling: truck([1, 2], 10, [2, 2, 3, 3, 5, 5, 8])
Calling: truck([1, 2, 2], 10, [2, 3, 3, 5, 5, 8])
Calling: truck([1, 2, 2, 2], 10, [3, 3, 5, 5, 8])
Calling: truck([1, 2, 2, 2, 3], 10, [3, 5, 5, 8])
1.Truck loaded with packages [1, 2, 2, 2, 3] => total weight=10

Remaining packages = [3, 5, 5, 8]
Now loading remaining packages on 2.Truck:
Calling: truck([], 10, [3, 5, 5, 8])
Calling: truck([3], 10, [5, 5, 8])
Calling: truck([3, 5], 10, [5, 8])
Calling: truck([3, 5], 10, [8])
Calling: truck([3, 5], 10, [])
2.Truck loaded with packages [3, 5] => total weight=8

Remaining packages = [5, 8]
Now loading remaining packages on 3.Truck:
Calling: truck([], 10, [5, 8])
Calling: truck([5], 10, [8])
Calling: truck([5], 10, [])
3.Truck loaded with packages [5] => total weight=5

Remaining packages = [8]

One the 1.truck are loaded more packages (than without sort) [1, 2, 2, 2, 3], on the 2.truck are loaded packages [3, 5] and on the 3.truck is loaded only one package [5].
But the weighty package [8] remains. Without sorting remains only lightweight package [2]. I don't know if it is more efficient?

I tried also your other suggestion

  ...
  packages = [5, 3, 8, 2, 1, 2, 3, 5, 2]
  packages.sort()
  packages.reverse()
  ...

Well, look at this - here the result seems to be optimaly

Original packages = [8, 5, 5, 3, 3, 2, 2, 2, 1]

Loading packages on 1.Truck:
Calling: truck([], 10, [8, 5, 5, 3, 3, 2, 2, 2, 1])
Calling: truck([8], 10, [5, 5, 3, 3, 2, 2, 2, 1])
Calling: truck([8], 10, [5, 3, 3, 2, 2, 2, 1])
Calling: truck([8], 10, [3, 3, 2, 2, 2, 1])
Calling: truck([8], 10, [3, 2, 2, 2, 1])
Calling: truck([8], 10, [2, 2, 2, 1])
Calling: truck([8, 2], 10, [2, 2, 1])
1.Truck loaded with packages [8, 2] => total weight=10

Remaining packages = [5, 5, 3, 3, 2, 2, 1]
Now loading remaining packages on 2.Truck:
Calling: truck([], 10, [5, 5, 3, 3, 2, 2, 1])
Calling: truck([5], 10, [5, 3, 3, 2, 2, 1])
Calling: truck([5, 5], 10, [3, 3, 2, 2, 1])
2.Truck loaded with packages [5, 5] => total weight=10

Remaining packages = [3, 3, 2, 2, 1]
Now loading remaining packages on 3.Truck:
Calling: truck([], 10, [3, 3, 2, 2, 1])
Calling: truck([3], 10, [3, 2, 2, 1])
Calling: truck([3, 3], 10, [2, 2, 1])
Calling: truck([3, 3, 2], 10, [2, 1])
Calling: truck([3, 3, 2, 2], 10, [1])
3.Truck loaded with packages [3, 3, 2, 2] => total weight=10

Remaining packages = [1]

Only the littlest package [1] remains. But it's because the total weight of the packages is sum(packages)=31 is greater that the total load of the all three trucks.
Trully, your suggestion leads to optimal solution.
I give you a star

 

[Catalys]

mikron,

It's easy to tell when a computational solution is optimal, but if you are talking about a real business situation, then "sorting" means spending additional time, effort, energy, sorting space, etc., BEFORE the trucks can be loaded.

Hence, your paper-optimal solution may be the costliest...

 

[mikrom]

Catalys,

Sure, you are right, but this was only an exercise of someone learning the recursion (see the link above), not a real business situation.
So regarding the optimality - the right word is paper-optimal as you said