[练习] 尺寸切割方案

rubyish

问题:
解决一个线材切割问题，
例如一根钢材10m，要切割2.5m，2.6m，1.9m三种尺寸，
剩下的废料要小于最小的尺寸。
有以下11种切割方案。

      sum    remain     2.5     2.6     1.9
01|  10.00   0.00       4       0       0
02|   9.70   0.30       0       3       1
03|   9.60   0.40       1       2       1
04|   9.50   0.50       2       1       1
05|   9.50   0.50       0       0       5
06|   9.40   0.60       3       0       1
07|   9.00   1.00       0       2       2
08|   8.90   1.10       1       1       2
09|   8.80   1.20       2       0       2
10|   8.30   1.70       0       1       3
11|   8.20   1.80       1       0       3

表述为数学形式就是，
10-（2.5a+2.6b+1.9c）< 1.9
10-（2.5a+2.6b+1.9c）>= 0

a,b,c=0,1,2,3....
写一个程序，求出这种算法的所有方案，即a,b,c的所有组合。
实际使用中，可能不止三种尺寸，视输入而定。
输出格式类似于表格，也可以转置成纵向表格，这样方便输出。

rubyish

v1: del~
v2:

1. nLENGTH  = 10
   
2. aCUT  = [ 2.5, 2.6, 1.9, 3.5, 2.0, 4.0, 4.5, 5, 4.7, 3.2 ]
   
3. aCUT.sort! {|a, b| b <=> a }
   
4. nMAX  = nLENGTH - aCUT.last
   
5. nNUM  = 0
   
6. 
   
7. puts ["%9s%10s" % %w[sum remain], *aCUT] * ?\t
   
8. aTRY = aCUT.map {|x| [*0 .. nLENGTH / x] }
   
9. aTRY.shift.product(*aTRY).reduce([]) {|r, s|
   
10.   nSUM, nI = 0, -1
    
11.   s.each do |si|
    
12.     nSUM += aCUT[nI += 1] * si
    
13.     break if nSUM > nLENGTH
    
14.   end
    
15.   r << [nSUM, nLENGTH - nSUM, *s] if nLENGTH >= nSUM &&  nSUM > nMAX
    
16.   r
    
17. }.sort {|a, b| b.first <=> a.first }.each {|x|
    
18.     puts "%03d|%7.2f%7.2f\t" % [nNUM += 1, *x.shift(2)] << x * ?\t
    
19.   }

复制代码

rubyish

v3:

1. #!/usr/bin/ruby
   
2. nlength = 10
   
3. adata = [ 5, 4.7, 4.5, 4.0, 3.5, 3.2, 2.6, 2.5, 2.0, 1.9 ]
   
4. adata.sort! {|a, b| b <=> a }
   
5. scount = 0
   
6. 
   
7. def kelect nlength, adata
   
8.   nmax, ncheck, nt, ni = nlength - adata[-1], 1, 1, -1
   
9.   arange = adata.map {|e| (0 .. nlength / e).to_a }
   
10.   aelem  = arange.map {|e| ncheck *= e.size; e.size }
    
11.   astep  = [1, *(1...aelem.size).map {|e| nt *= aelem[-e] }].reverse!
    
12.   acollection = []
    
13. 
    
14.   while (ni += 1) < ncheck
    
15.     anum = (0...aelem.size).map {|i| arange[i][ni / astep[i] % aelem[i]] }
    
16.     nsum = 0
    
17. 
    
18.     for i in 0...aelem.size
    
19.       nsum += adata[i] * anum[i]
    
20.       next if nsum <= nlength
    
21.       njump = (aelem[i] - anum[i]) * astep[i]
    
22.       ni += njump - 1
    
23.       break
    
24.     end
    
25. 
    
26.     acollection << [nsum, nlength - nsum, anum] if
    
27.       nlength >= nsum && nsum > nmax
    
28.   end
    
29.   acollection
    
30. end
    
31. 
    
32. puts "%4s%5s%7s\t" % ['', 'sum', 'rem'] << adata * ?\t
    
33. kelect(nlength, adata).sort {|a, b| b[0] <=> a[0] }.each do |e|
    
34.   print '%03i'% scount += 1, "| %5.1f%7.2f\t" % e.shift(2), e * ?\t, ?\n
    
35. end
    
36. 
    

复制代码