Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   перебор всех сумм n-го количества членов массива (http://www.flasher.ru/forum/showthread.php?t=142033)

Elff 10.07.2010 21:57

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

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++) {
 
}

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

iNils 10.07.2010 22:14

Цитата:

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

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

Elff 10.07.2010 22:51

Цитата:

Сообщение от iNils (Сообщение 921293)
Можно узнать с какой целью?

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

iNils 10.07.2010 23:09

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

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

Elff 10.07.2010 23:29

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

iNils 11.07.2010 00:24

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

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

-De- 11.07.2010 00:37

Вообще, если один элемент может встречаться 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 11.07.2010 00:48

Цитата:

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

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

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- (Сообщение 921320)
Только я думаю хотят не переборное решение, если это не реальные трубы %) Целые ли длины труб? Какая вообще точная формулировка? %)

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

-De- 11.07.2010 01:11

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

Nirth 11.07.2010 01:15

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

iNils 11.07.2010 01:44

Согласен с Nirth, при максимальном числе труб 24 при выборе из 30 труб, получится 30^24 = 2,82429536481e+35 вариантов.

-De- 11.07.2010 06:30

Да строит оно трубу на 100км за полсекунды на флэше и не жужжит. Зачем сервер нагружать?

Elff 11.07.2010 19:25

-De-, iNils, спасибо за помощь :drinks:

Остановился пока на таком варианте, надо будет доработать потом...
Код AS3:

var my_length:int = 2500; // 25 м
var cut_Ar:Array = [102,110,120,125,127,131,137,143,161,176,199,200,250,256,277,300,321,349,351,380,385,387,390];
var index_Array:Array = []; // массив с индексами нужных длин в массиве cut_Ar
var ind:int = cut_Ar.length-1;
var limit:int = 10; // допуск
function rundown():void {
        var max_cutAr:int = cut_Ar[ind];
        var min_numPipe:uint = Math.ceil(my_length/max_cutAr); // минимальное количество труб
        for (var j:int = ind; j>=0; j--) {
                if (min_numPipe<=ind) {
                        var long:int = cut_Ar[j];
                        var long_minus:int = cut_Ar[j-1];
                        if (long<my_length+limit) {
                                my_length-=long;
                                index_Array.unshift(j);
                        }
                        if (my_length<=limit && my_length>=-limit) {
                                trace("метраж: " + Number(2500-my_length))
                                for (var q:int=0; q<index_Array.length; q++) {
                                        trace(cut_Ar[index_Array[q]])
                                }
                                //break;
                        }
                        if (my_length<long_minus-limit) {
                                my_length+=long;
                                index_Array.splice(0,1);
                        }
                        if (my_length<=limit && my_length>=-limit) {
                                trace("метраж: " + Number(2500-my_length))
                                for (var q2:int=0; q2<index_Array.length; q2++) {
                                        trace(cut_Ar[index_Array[q2]])
                                }
                                //break;
                        }
                        if (j==0) {
                                index_Array = [];
                                my_length = 2500;
                                ind--;
                                rundown();
                        }
                } else {
                        break;
                }
        }
}
rundown();

Цитата:

Сообщение от -De- (Сообщение 921325)
ссылка (можно в личку) на риальнэ трубопродавальный сайт =)

Серьезно?:) могу написать, только сайт мягко говоря убогенький

Котяра 11.07.2010 23:53

ужасные наименования. глаза ломает.
Код AS3:

max_cutAr
cut_Ar
index_Array

вы уж определитись со стилем..

-De- 12.07.2010 00:08

Не интересно с допуском!
Вот, раз уж я накидал, чтоб посмотреть, за сколько же оно считает, мож пригодится.
Код AS3:

                public var C:Array = [102, 120, 125, 127, 131, 133, 139, 143, 160, 177, 199, 250, 256, 277, 321, 349, 351, 385, 387, 390];
                public var sum:int = 100009;
                public var A:Array;
 
                private function init(e:Event = null):void
                {
                        removeEventListener(Event.ADDED_TO_STAGE, init);
                        A = new Array(sum + 1);
                        A[0] = 0;
                        C.sort(2);//сортируем по убыванию, чтоб самые длинные трубы использовались чаще всего
                        for (var i:int = 0; i < C.length; ++i) {
                                for (var j:int = 0; j <= sum - C[i]; ++j) {
                                        if (A[j] != null && A[j + C[i]] == null) {
                                                A[j + C[i]] = C[i];
                                                if (j + C[i] == sum) {
                                                        printTubes();
                                                        return;
                                                }
                                        }
                                }
                        }
                        trace("not found");
                }
                private function printTubes():void {
                        var count:int = 0;
                        for (var i:int = sum; i > 0; i -= A[i]) {
                                count += A[i];
                                trace("труба длиной "+A[i]+" метраж "+count);
                        }
                        A = null;
                        //trace(count);
                }

Ссылка на сайт интересна в плане, что не олимпиада какая.


Часовой пояс GMT +4, время: 11:01.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.