SHARE
TWEET

Untitled

a guest Aug 25th, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random, collections
  2.  
  3. sizes = [6, 6.6, 7.2, 7.8, 8.4, 9.6, 12]
  4.  
  5. beams = {
  6.     3.6: 6,
  7.     6.7: 37,
  8.     5.5: 4,
  9.     7.2: 37,
  10.     1.1: 2,
  11.     3.2: 9,
  12.     2.9: 2,
  13.     4.6: 3,
  14.     4.9: 15,
  15.     1.2: 10,
  16.     5.9: 4,
  17.     4.3: 4,
  18.     1.5: 1,
  19.     2.2: 2,
  20.     3.1: 4,
  21.     3.4: 4,
  22.     1: 4,
  23.     1.6: 2,
  24.     1.8: 3,
  25.     1.9: 2,
  26. }
  27.  
  28. sizes = [float(x) for x in sizes]
  29. beams = [float(x) for k, v in beams.items() for x in [k] * v]
  30.  
  31. def greedy_asc(size, beams):
  32.     return greedy_beam(size, sorted(beams))
  33.  
  34.  
  35. def greedy_des(size, beams):
  36.     return greedy_beam(size, sorted(beams, reverse=True))
  37.  
  38.  
  39. def greedy_shuffle(size, beams):
  40.     random.shuffle(beams)
  41.     return greedy_beam(size, beams)
  42.  
  43.  
  44. def greedy_beam(size, beams):
  45.     used = []
  46.     for b in beams:
  47.         if b > size:
  48.             continue
  49.         size -= b
  50.         used.append(b)
  51.     if not used:
  52.         return 100, used
  53.     return (size, used)
  54.  
  55.  
  56. def generate_order(sizes, beams):
  57.     beams = beams[:]
  58.     total_wastage = 0
  59.     order = []
  60.     while beams:
  61.         best = (100, 100, [])
  62.         for s in sizes:
  63.             for f in [greedy_asc, greedy_des, greedy_shuffle]:
  64.                 waste, used = f(s, beams)
  65.                 if waste < best[0]:
  66.                     best = (waste, s, sorted(used))
  67.         total_wastage += best[0]
  68.         order.append(best)
  69.         for b in best[2]:
  70.             beams.remove(b)
  71.     return (total_wastage, order)
  72.  
  73.  
  74. best = (100, [])
  75. for i in range(1000):
  76.     if i % 50 == 0:
  77.         print(i, "...")
  78.     cand = generate_order(sizes, beams)
  79.     if cand[0] < best[0]:
  80.         best = cand
  81.         print("candidate order %d with wastage %.1f" % (i, cand[0]))
  82. print()
  83.  
  84. counts = collections.defaultdict(int)
  85. summary = collections.defaultdict(int)
  86. orders = sorted((size, waste, order) for waste, size, order in best[1])
  87. for size, waste, order in orders:
  88.     counts[size] += 1
  89.     summary[
  90.         ("beam size %.1f for beams %s with wastage %.1f" % (size, order, waste))
  91.     ] += 1
  92.  
  93. print("order description:")
  94. for s, count in sorted(summary.items()):
  95.     print(count, "x", s)
  96. print()
  97.  
  98. print("order summary:")
  99. for s, count in sorted(counts.items()):
  100.     print(count, "x", s)
  101. print()
  102.  
  103. print("total wastage %.1f" % best[0])
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top