LINUX.ORG.RU
Форум — Talks  

Раскройка металла без смс

 ,


0

1

Существует ли вообще в принципе опенсорсная софтина для решения простейшей задачи - вписки N прямоугольных заготовок в лист заданного размера с получением минимального кол-ва обрезков?

Или задача о наполнении рюкзака вообще неподъёмна, лучше ещё один виндовманагер написать?

☆

Последнее исправление: svr4 (всего исправлений: 1)
← Виртолёты(ноне квадрокоптеры и опасне беспилотники)
Я напишу тебя на Java →

Или задача о наполнении рюкзака вообще неподъёмна

А что там такого сложного? Какие-то алгоритмы задач семейства оптимального раскроя делаются как лаба на одной паре с тремя перекурами и походом в столовку.

Igron ★★★★★
()
Ответ на: комментарий от Igron

А что там такого сложного? Какие-то алгоритмы задач семейства оптимального раскроя делаются как лаба на одной паре с тремя перекурами и походом в столовку.

Ага, особенно раскрой фанеры и тканого материала. Студенты такие умные пошли...

andreyu ★★★★★
()
Ответ на: комментарий от Igron

Ну я вот к тому что почему-то считается что каждый должен сделать очередной оконный менеджер, убунту с нескучными обоями или собрать ведро не так, а эдак. При этом даже такой простейшей программы до сих пор не видать. Я уж не заикаюсь о функционале серьёзных CAD, который лично мне не нужен - всё равно вместо станков с ЧПУ работают таджики.

svr4 ☆
() автор топика

Напиши еще одну реализацию. Если у тебя заготовок N, то за вполне разумное время M ты тупым перебором найдешь оптимальное размещение. А если ты еще и что-нибудь эдакое воткнешь (т.е. почитаешь пару-тройку статей сначала), то время сократится до K, что на P заготовках будет быстрей мгновения!

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от svr4

На фанеру емнип допуск на пропил, да ориентация заготовок, не?

Да, ориентация. Но не только для максимального заполнения площади.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Добавлю ещё в копилку зеркалирование — для плоских материалов (фанера) это может быть уместным. (Но может быть не технологичным.)

beastie ★★★★★
()
Ответ на: комментарий от svr4

Ну я вот к тому что почему-то считается что каждый должен сделать очередной оконный менеджер, убунту с нескучными обоями или собрать ведро не так, а эдак.

Знаешь, как проверить, что «каждый должен сделать»? Если на выходе получится бабло, значит должен. Иначе — страдание ерундой. Та же мастурбация, но в особо извращенной форме.

Свежий пример: сегодня пять человек (среди них трое с инженерной вышкой) весь вечер угробили на то, чтоб заставить кривую программу для АЗС работать. Не получилось: заправка будет стоять как минимум до завтрашнего полудня. Не то, чтоб программа очень простая, но разработчик гребет деньги лопатой даже за очень кривую реализацию. В общем, ты понял. Дерзай.

Igron ★★★★★
()

pack.rb 

class Array
  def delete_first item
    delete_at index(item)
  end

  def rotate
    d = dup
    d.push d.shift
    d
  end
end

class Trunk
  def initialize(w,h)
    @w = w
    @h = h
    @items = []
    @rows = (1..@h+2).map{ "_"*(@w+2) }
  end

  def add box
    try_adding(box) or try_adding(box.rotate)
  end
  def try_adding box
    boxrow = "_"*(box[0]+2)
    @rows.each_with_index{|r,i|
      break if i > @rows.size - (box[1]+2)
      next unless r.include?(boxrow)
      idxs = @rows[i+1, box[1]+1].map{|s| s.index boxrow }
      next unless idxs.all?
      idx = idxs.max
      next unless @rows[i, box[1]+2].all?{|s| s[idx,boxrow.size] == boxrow }
      @rows[i+1, box[1]].each{|s|
        s[idx+1, box[0]] = "#" * box[0]
      }
      @items.push box
      return box
    }
    nil
  end

  def empty?
    @items.empty?
  end
  def to_s
    @rows[1..-2].map{|r|r[1..-2]}.join("\n")
  end
end

trunk = gets.strip.split("x").map{|i| i.to_i}
boxes = gets.strip.split(" ").map{|s| s.split("x").map{|i| i.to_i} }

boxes = boxes.sort_by{|b| b.inject{|f,i| f*i} }.reverse
trunks = [Trunk.new(*trunk)]
until boxes.empty?
  fitting = boxes.find{|box| trunks.last.add box }
  if fitting
    boxes.delete_first fitting
  elsif trunks.last.empty?
    raise "Can't fit #{boxes.inspect} into the trunk"
  else
    trunks << Trunk.new(*trunk) unless boxes.empty?
  end
end
puts
puts trunks.join("\n\n")

input.dat 

50x40
9x10 15x16 9x10 15x16 17x12 17x12 9x10 9x10 10x16 7x8 10x10

ruby pack.rb < input.dat

output: 

###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
###############_###############___________________
###############_###############_#################_
###############_###############_#################_
###############_###############_#################_
________________________________#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########_#################_
##########_##########_#########___________________
##########_##########_#########_#########_#######_
##########______________________#########_#######_
##########_#########_#########__#########_#######_
##########_#########_#########__#########_#######_
##########_#########_#########__#########_#######_
##########_#########_#########__#########_#######_
##########_#########_#########__#########_#######_
___________#########_#########__#########_#######_
___________#########_#########__#########_________
___________#########_#########__#########_________
___________#########_#########____________________
___________#########_#########____________________
__________________________________________________
__________________________________________________

sdio ★★★★★
()
Ответ на: комментарий от svr4

простейшей программы до сих пор не видать

Не видать — напиши, тем более она простейшая.

PolarFox ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Виртолёты(ноне квадрокоптеры и опасне беспилотники)
Talks
Я напишу тебя на Java →