перебор всех сумм n-го количества членов массива

[Elff]

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

var my_number:uint = 5;
var Ar:Array = [102,120,125,127,131,133,139,143,160,177,199,250,256,277,321,349,351,385,387,390];
for (var i:int = 0; i<Ar.length; i++) {
 
}

Никак не соображу как бы это сделать...

[iNils]

Нужно перебрать все варианты сумм

Можно узнать с какой целью? Просто для 5 чисел из 20, это 1'860'480 комбинаций (20*19*18*17*16).

Добавлено через 12 минут
Вру. 759'375 (15*15*15*15*15)

[Elff]

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

Можно узнать с какой целью?

нужно будет подбирать определенный метраж
...многовато, конечно, получается, массив может и больше быть
все перебирать скорее всего не придется, если искомая сумма(+/-) будет найдена, то можно будет цикл остановить

[iNils]

Да что же такое Опять не правильно посчитал, будет 16^5 = 1'048'576, но это при том, что одно число не может использоваться дважды или более, если может, то будет еще больше 20^5 = 3'200'000.

нужно будет подбирать определенный метраж

А подробнее можно? Возможно алгоритм можно оптимизировать, но для этого нужно дать полные условия.

[Elff]

Есть общий массив с длинами труб, из него нужно будет подобрать определенный метраж,трубы должны быть определенной длины (от и до). В массив Ar добавляются трубы нужной длины. Исходя из минимальной и максимальной длины можно посчитать сколько будет труб (допустим от 5 до 6). И дальше планировалось перебирать все члены массива Ar сначала по 5 штук, потом, если потребуется по 6. Или остановить, когда будет найдено...как-то так

[iNils]

Как-то все равно не понятно. Скажем нужна длина 750, можно взять трубу 250 * 3, а можно 125 * 6. Поэтому мне кажется, что вы не с того конца начинаете (я про количество труб).

Исходя из минимальной и максимальной длины можно посчитать сколько будет труб

Если взять 5 труб минимальной длины (102), то общая длина будет 510, а 5 труб максимальной длины (390) - 1950. Разница почти в 4 раза, что и на число труб влияет.

[-De-]

Вообще, если один элемент может встречаться 1 раз, то число вариантов есть (по определению, т.к. порядок элементов в сумме не важен) число сочетаний из 20 по 5, т.е. (20!/(15!*5!)) = 20*19*18*17*16/(1*2*3*4*5) = 15504. Если может встречаться 5 раз, то задача подсчёта сводится к "найти число способов разложить n одинаковых шаров по m разным корзинам", где n = 5, m = 20. Ответ (задачка известная, накрайняк - гуглится Upd: блин, оно же и в вики есть) - C(m + n - 1, n) = 42504.
Собсно идея решения задачи - берётся 19 перегородок и между ними расставляется 5 шаров. Она же может использоваться для переборного решения. Только я думаю хотят не переборное решение, если это не реальные трубы %) Целые ли длины труб? Какая вообще точная формулировка? %)

[Elff]

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

Как-то все равно не понятно. Скажем нужна длина 750, можно взять трубу 250 * 3, а можно 125 * 6.

Ну да, все верно, начинаем перебор с расчетом отдать меньше труб, попадается вариант 250*3, отдаем его и заканчиваем

var min:int = 100; // длины от min
var max:int = 400; // до max
var my_length:int = 2500; // нужен метраж 25 м
 
var Ar:Array = [065,099,102,110,120,125,127,131,133,139,140,141,142,143,143,144,160,177,199,200,250,256,277,300,321,349,351,380,385,387,390,405,409,430,450,450,501,505,510];
var cut_Ar:Array = [];
for (var i:int = 0; i<Ar.length; i++) {
	if (Ar[i]>=min && Ar[i]<=max) {
		cut_Ar.push(Ar[i]);
	}
	if (Ar[i]>max) {
		break;
	}
}
var min_cutAr:int = cut_Ar[0];
var max_cutAr:int = cut_Ar[cut_Ar.length-1];
trace(Math.ceil(my_length/max_cutAr)+" - минимальное количество труб");
trace(Math.floor(my_length/min_cutAr)+" - максимальное количество труб");

С количеством труб это для оптимизации - чтобы не перебирать ненужные варианты. В этом примере количество может быть от 7 до 24, нет смысла перебирать варианты с 1 до 6 труб и больше 24

Сообщение от -De-

Только я думаю хотят не переборное решение, если это не реальные трубы %) Целые ли длины труб? Какая вообще точная формулировка? %)

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

[-De-]

Собсно вот ваша задачка, с вас пиво ссылка (можно в личку) на риальнэ трубопродавальный сайт =)
PS: если длины труб не целые, то ужос ивсётакое.

[Nirth]

А зачем это делать на ActionScript?
На сервере, с Java/C было бы быстрей, а на логических языках вроде Prolog/Mercury лаконичней