że problem tenzbiór S liczb n - istnieje podzbiór z prawdopodobieństwa każdego elementu S występujące w nim równa
Teraz otrzymuje zbiór S liczby n. Musisz wybrać podzbiór S 'z liczb k od S tak, że prawdopodobieństwo każdego elementu S występującego w S' jest równe (tj. Każdy jest wybierany z prawdopodobieństwem k/n). Możesz wykonać tylko jedno przejście przez liczby. Co jeśli n jest nieznany?
i nawet ma rozwiązanie: http://www.algorithm.cs.sunysb.edu/algowiki/index.php/TADM2E_2.43
Nadal: I nie rozumieją tekstu w ogóle problem.
Otrzymałem zestaw S n liczb. W porządku. Muszę wybrać podzbiór (możliwe są 2^n podzbiorów) liczby k tak, że prawdopodobieństwo każdego elementu S występującego w S 'jest równe ... oczywistą odpowiedzią byłoby odebranie pustego zestawu S' : każdy element w S miałby 0 prawdopodobieństwo, aby znaleźć się w S '.
Jeśli jest to niedopuszczalne (i powinno być powiedziane), przypuszczam, że powinienem liczyć na najbardziej powtarzający się element (pojawiający się T razy) w S i sprawić, aby każdy inny element miał dokładnie T wystąpienia w S '(to powinien nadal być podzbiorem, jeśli elementy są zawarte w S).
Naprawdę nie rozumiem rozwiązania kolejki priorytetowej ani prawdopodobieństwa k/n. Czy ktoś może mi w tym pomóc?
Kiedy mówią, że każdy element wymaga równego prawdopodobieństwa, oznacza to, że każdy element jest odrębny. Nawet jeśli masz zestaw '{1, 2, 2, 3}', dwa '2' są osobnymi elementami, które wyglądają tak samo, ale nie są. Twój akapit na temat 'T instances' zmierza w złym kierunku, ponieważ myślisz o tych' 2'ach jako o tym samym elemencie. Dla uproszczenia wyobraź sobie zestaw programisty, w którym elementy mogą wystąpić tylko raz. – dwanderson