Задача о стене

[rrrFer]

А блоки нет . Разбитие стены на независимые прямоугольные участки по мне годное решение.

Смотри на предыдущей странице, я уже приводил пример.

Разбиение стены на независимые прямоугольные участки - это было бы идеальное решение. Только для произвольной стены такое разбиение выполнить невозможно. Ключевое слово при этом - НЕЗАВИСИМЫЕ.

[Utkin]

Ключевое слово при этом - НЕЗАВИСИМЫЕ.

Да это автоматически отметает некоторые решения. Сужает возможное число вариантов. Но не факт, что те варианты действительно годные. В общем надо думать. Да и в случае неудачи можно вертикальные к примеру пересмотреть в горизонтальные.

[Yazon2006]

Существует легенда, что Junior Java Developer может решить такую задачу, написать рабочий код, и документацию за двое суток. А посему есть мнение, что существует более изящное решение данной задачи, либо джуны нынче шибко грамотные пошли...

[evg_m]

что Junior Java Developer может решить такую задачу, написать рабочий код, и документацию за двое суток.

РЕКУРСИЯ
берем блок, укладываем,(перебираем все варианты) получаем стену другой конфигурации, но меньшей площади.
и начинаем снова на "новой" стене с "новым" набором блоков, до тех пока не получим стену нулевой площади. (или не сможем найти подходящий блок).

НО, работать (до получения результата) эта программа будет 1 млрд. лет.

http://programmersforum.ru/showthrea...87#post1508787
Время написания программы ~30 мин. (включая время отладки!!)
Время работы программы до получения результата ....?

[Yazon2006]

Я понимаю суть перебора, но не знаю как это реализовать. Рекурсия всегда была моим слабым местом. Кроме того их вращать можно (кирпичи), а это вообще выводит меня из состояния душевного спокойствия =)

[evg_m]

TStena =class;
TBlock =class;
Tblocks =array of TBlock;// TObjectList;

function Most(stena: TStena; blocks: TBlocks): boolean;
begin
  result:=true;
  if stena.Square =0 then Exit; //стена имеет НУЛЕВУЮ площадь и стало быть ничего болле укладывать НЕ НАДО.
  
result:=false;
for j:=0 to blocks.Length-1 do begin // перебираем ВСЕ доступные нам блоки
  for x:=0 to steha.with-1 do begin // перебираем ВСЕ возможные позиции нового по горизонтали
     for y:=0 to stena.hight-1 do begin // позиции по вертикали
        for z:=0 to 3 do begin //разные расположения блока НА ОДНОМ месте (4 поворота) если будут еще и перевороты зеркальные отражения то надо изменить на 7 ???
         stn:=MostBlock(stena, blocks[j], x, y, z); // УКЛАДКА выбранного(j) блока на выбранное(x,y) место выбранным(z) образом!!
// в результате получаем НОВУЮ стенку или НИЧЕГО если уложить указанным образом НЕВОЗМОЖНО (закрываем дырки/выход за стенку/наложение)
    if stn<>nil then begin // при успешном размещении блока 
     // делаем все тоже самое , но уже для новой стенки !!та самая РЕКУРСИЯ !!!
       result:=Most(Stn, blocks); // список блоков оставляем прежним (СЧИТАЕМ что КОЛИЧЕСТВО блоков КАЖДОГО формата у нас не ограничено
    if result then break; // У НАС ПОЛУЧИЛОСЬ и мы радостно заканчиваем КАЖДЫЙ из переборов
 end;
 if result then break;
end;
 if result then break;
end;
if result then break;
end;

end;

В теме по ссылке есть готовый и рабочий код.
алгоритмически почти идентичный приведенному.

[Yazon2006]

Хм! Красота) Но! Действительно таки долго наверное будет делаться)
я вот кстати погуглил по этому поводу и нашёл:
Руднев Антон Сергеевич "Алгоритмы локального поиска для задач двумерной упаковки"
А именно РАЗДЕЛ 2. Алгоритм имитации отжига для задач прямоугольной упаковки в контейнеры с запрещенными областями.
ИМХО, это то что надо.

[Yazon2006]

Сообщение от evg_m

СЧИТАЕМ что КОЛИЧЕСТВО блоков КАЖДОГО формата у нас не ограничено

А количество блоков таки задано конкретно для каждого конкретного размера (

[Yazon2006]

Пока были силы что то получалось, но в каком то месте не работает. На дебаг сил не хватило.

import java.util.ArrayList;


public class Upakovka {
    private static class Stena {
        public byte [][] array = new byte[][] {
                {0, 1, 0, 1, 1, 0, 1, 0},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1},
        };

        public Stena(Stena stena) {
//            array = stena.array;
            System.arraycopy(stena.array, 0, array, 0, stena.array.length );
        }

        public Stena() {

        }

        int getWidth() {
            return array[0].length;
        }

        int getHeight() {
            return array.length;
        }

        int getSquare() {
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                for (int j = 0; j < array[i].length; j++) {
                    if(array[i][j] == 1) count++;
                }
            }
            return count;
        }

        public boolean cut(Block block, int x, int y, int z) {
        	if(!check(block, x, y, z))
        		return false;
            int w = z == 0 ? block.getWidth() : block.getHeight();
            int h = z == 0 ? block.getHeight() : block.getWidth();
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
//                	if(array[x+i][y+j] == 0) return false;
                    array[x+i][y+j] = 0;
                }
            }
            return true;
        }
        
        public boolean check(Block block, int x, int y, int z) {
            int w = z == 0 ? block.getWidth() : block.getHeight();
            int h = z == 0 ? block.getHeight() : block.getWidth();
            if(y + h > getWidth()) return false;
            if(x + w > getHeight()) return false;
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                	if(array[x+i][y+j] == 0) return false;
                }
            }
            return true;
        }
    }

    private static class Block {
        private int width;
        private int height;

        Block(int width, int height) {
            this.width = width;
            this.height = height;
        }

        public int getWidth() {
            return width;
        }

        public int getHeight() {
            return height;
        }
    }

    private static boolean Most(Stena stena, Block[] blocks) {
        boolean result = true;
        if(stena.getSquare() == 0) {
            // Exit;
        }
        result = false;
        for (int j = 0; j < blocks.length - 1; j++) {
            for (int x = 0; x < stena.getWidth() - 1; x++) {
                for (int y = 0; y < stena.getHeight() - 1; y++) {
                    for (int z = 0; z < 2; z++) {
                        Stena stn = MostBlock(stena, blocks[j], x, y, z);
                        if(stn != null) {
                            result = Most(stn, blocks);
                        }
                        if(result) break;
                    }
                    if(result) break;
                }
                if(result) break;
            }
            if(result) break;
        }
        return result;
    }

    private static Stena MostBlock(Stena stena, Block block, int x, int y, int z) {
		Stena newStena = new Stena(stena);
        if(newStena.cut(block, x, y, z))
       		return newStena;
        else
        	return null;
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
        Stena stena = new Stena();
        ArrayList<Block> list = new ArrayList<>();
        list.add(new Block(3, 4));
        list.add(new Block(3, 4));
        list.add(new Block(3, 4));
        list.add(new Block(3, 4));
        list.add(new Block(3, 4));
        
        list.add(new Block(1, 3));
        
        list.add(new Block(2, 1));
        list.add(new Block(2, 1));
        list.add(new Block(2, 1));
        list.add(new Block(2, 1));
        list.add(new Block(2, 1));
        list.add(new Block(2, 1));
        
        list.add(new Block(1, 1));
        list.add(new Block(1, 1));
        list.add(new Block(1, 1));
        list.add(new Block(1, 1));

        boolean res = Most(stena, list.toArray(new Block[list.size()]));
        System.out.print(res);
	}

}

[Yazon2006]

Хотя конечно это все бред! Количество блоков в наличии не учитывается, и даже если найти баг из-за которого оно не перебирает все варианты, то stackoverflow гарантирован.