мат кол-во невидимых блоков

[in4core]

Собственно как то давно создавал похожую тему, просто щас конкретно допер где глюк.

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

Как считал кол-во страниц :

private function getListCount():Number {
 
			var h:int = 0;
			var h1:int = _stage.stageHeight - _mainContainer.y;
 
			for (var i:int = 0; i < _eVector.length; i++) {
 
				if (i) h += _eVector[i].height + 15;
				else   h += _eVector[i].height;
			}
 
			var lists:Number = h / h1;
 
			if (lists < 0) lists = 1;
			else if ( int(lists) < lists ) lists = int(lists) + 1;
 
			return lists;
		}

Считало поидее верно, но есть нюанс о котором я не знал до этого :
Допустим на первой странице поместилось 3 спрайта, а 4 спрайт очень большой и занял всю вторую страницу, на 3й странице появился маленький спрайт, но фишка в том, что этот маленький спрайт совершенно легко мог быть помещен на 1 страницу в свободное место, поэтому такая система считает, что страниц всего 2, а не 3.
Вот думаю как лучше решить, наверное стоит сначала сортировать вектор по мин > макс высоте , а потом только прогонять в цикле. или есть лучше решение?

[TanaTiX]

Где-то была тема по наиболее оптимальному заполнению прямоугольной области фигурами. Там это было необходимо для текстурирования, и там давали ссылки на алгоритмы. Думаю это должно помочь.

Upd. а вообще можно так реализовать
из массива значений берем максимальное, если место осталось - перебираем максимальное из подходящих и так далее. А при переходе на новую страницу просто page++.

[dsQuadro]

может лучше считать листы при их формировании а не отдельной функцией?

[in4core]

Данные динамические постоянно обновляются значит и листы постоянно обновляются.

TanaTiX - а разве вариант сортировки не поможет, как я предложил?

[Dukobpa3]

Сортировка не спасет.

Например есть спрайты с размерами:
5
4
3
2

Отсортированные.
Размер страницы восемь.
Туда влезет 5 + 3, но не 5+4. В итоге упрешься в то же что у тебя сейчас.

[in4core]

Наверное немного не так
сортируем 2,3,4,5 размер 8.
страница 1 : 2 + 3
страница 2 : 4 ( ибо 4 + 5 не выйдет, а 2 и 3 уже просчитано )
страница 3: 5
все четко

[TanaTiX]

В зависимости от количества элементов, разница между реальностью и расчетным количеством может накапливаться. Поэтому лучше это делать при построении страниц. К тому же алгоритм практически одинаков.

Добавлено через 23 минуты
Наверняка не самый лучший вариант, но на скорую руку...

var h:int = 8;
var arr = [2,4,5,3];
var list:int=0;
arr.sort(Array.DESCENDING);
getList();
function getList():void{
	if(arr.length==0){
		trace("length", list);
		return;
	}
	if(arr[0]>h){
		list++;
		arr.shift();
	}else{
		if(arr.length==2){
			arr.pop();
		}else{
			if(arr.length>1){
				for(var i:int=arr.length - 1; i>1; i--){
					if(arr[0]+arr[i]==h || (arr[0]+arr[i]>h && i!=arr.length - 1)){
						arr.splice(i, 1);
						break;
					}
				}
			}
		}
		arr.shift();
		list++;
	}
	getList();
}

[-De-]

Задача о рюкзаке?

[in4core]

TanaTiX да, алгоритм тяжелый получился если лучше не придумаю придется наверное так

[TanaTiX]

алгоритм тяжелый получился

При желании можно и без рекурсии одним проходом. Допиливать наверняка есть что. Но по сути будет тоже самое. В плане производительности нужно иметь хотя бы альтернативу для сравнения.