zliczanie liczb do n*1000 - konkurs amino

Witam wszystkich,
mam pytanie i wielka prośbę do expertów programowania a mianowicie:
potrzebuje zsumować te liczby: 333 3509 440 1540 1617 330 1320 220 1298 1650 2035 2794 1243 2772 3575 264 1826 3311 440 3694 2222 671 2233 3751 3553
w sposób taki aby każda z liczb nie była wykorzystana więcej niż jeden raz oraz za zadanie jest otrzymać wynik jeden z tych: 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
podsumowując: niektóre liczby wymienione na początku trzeba tak pododawać aby wyszedł wynik (wielokrotność 1000 aż do 10000włącznie)

nie jest mi to potrzebna do szkoły itp po prostu zbieramy ze znajomymi kody z zupek amino i może los by sie w końcu uśmiechną do mnie:D

ps. może się tak zdarzyć ze nie będzie można spośród liczb ułożyć oczekiwanego wyniku.

pozdrawiam i z nadzieją oczekuję na kogoś kto umili mi czas przed świętami (oszczędzi mi czasu poświęconego na liczenie ręczne - bo kombinacji jest dużo

można by w pętli spróbować. pętla malejąca, każda dekrementacja co jeden tysiąc. od 10.000 lub więcej jesli potrzeba. i mysle ze dalej by trzeba było ręcznie wpisywać liczby które podałeś. można to obsłużyć kodem aby program mógł by odejmować od tej liczby, albo z sumować najpierw wszystkie i odjąć od nich tą okrągłą liczbe w tysiącach.

tak czy inaczej trzeba je wszystkie wpisać.

nic innego mi nie przychodzi do głowy.

mam nadzieje że pomogłem.

A zwróciłeś uwagę, że wszystkie liczby są wielokrotnością 11? ; )

Miłego sumowania.

eryk1985 napisał(a)

niektóre liczby wymienione na początku trzeba tak pododawać aby wyszedł wynik (wielokrotność 1000 aż do 10000włącznie)

na to nie zwróciłem uwagi :/

więc ten algorytm odpada.

ale już nasuną mi się inny pomysł. trzeba przypisać wszytko do tablic (wiem że trochę pracochłonne) można losować liczbę, która będzie wskazywać liczbę którą należy dodać do poprzedniej sumy (lub do zera, na początku lub do pierwszej liczby, innymi słowy do zmiennej która jest sumą). wszytko to w pętli która będzie sprawdzać czy już nie nastąpiła ta liczba co chcemy. trzeba się zabezpieczyć aby nie maksymalna ilość wykonań pętli nie był większy niż index tablicy -1; jak się nie uda to ponownie. na pewno będą inne możliwości jeśli zainicjujemy "ziarno"

Murky napisał(a)

A zwróciłeś uwagę, że wszystkie liczby są wielokrotnością 11? ; )

Miłego sumowania.

a 333 to według Ciebie liczba podzielna przez 11 bez reszty?

Dobra, 2 liczby z 25 nie są podzielne przez 11 :) Amino wie co robi.

To masz algorytm:

1. Wyodrębnij wszystkie liczby niepodzielne przez 11 i niech utworzą one zbiór A (tutaj 333 i 3694)
2. Stwórz zbiór wszystkich możliwych kombinacji liniowych elementów ze zbioru A postaci: k1a1 + k2a2 + ... + kN*aN, gdzie a1,...,aN to elementy zbioru A, a k1,...,kN to odpowiednie współczynniki mogące przybierać wartości 0,1,...,Ki, gdzie Ki oznacza ilość uzbieranych plakietek z wartością ai. Oznaczmy zbiór wszystkich kombinacji przez B.
3. Kolejno od każdej liczby ze zbioru {1000*n, n=1,...,10} odejmuj liczby ze zbioru B i spr podzielność przez 11, jeśli dana liczba jest podzielna przez 11 to wrzucaj ją do C.
4. Jeśli w C jest jakikolwiek element, to nawet masz znikomą szansę wygrać ;)

Pewnie mozna by to jakoś dalej ładnie matematycznie rozważać, ale mi się nie chce. A to co dalej musisz zrobić to spróbować ze swoich podzielnych przez 11 liczb ułożyć którąś z liczb ze zbioru C.

Murky napisał(a)

A zwróciłeś uwagę, że wszystkie liczby są wielokrotnością 11? ; )

no faktycznie a ta 333 to albo błąd kolegi albo wypuszczaja raz na jakis czas cos innego:)
to moim zdaniem nie ma sensu dalsze liczenie bo i tak nie przyniesie to oczekiwanej liczby:( chyba ze sie myle?
ps. cwaniaki z nich sa:P

Nie, z tego co wiem jest w puli pewna ilość niepodzielnych przez 11 liczb. Z tym że nie ma ich dużo. Zresztą jak sam widzisz ;) U Ciebie to są tylko 333 i 3694 (o ile nie ma błędu).

Ale nawet jeśli szanse są znikome i nie ma sensu liczenie na wygraną, to imo ma sens rozwiązanie ciekawego problemu algorytmicznego :) Choćby dla poćwiczenia sobie.

W powyższym przykładzie masz na razie tylko 25 różnych kodów więc jeszcze nie jest tak tragicznie. Ponieważ jednak ilość wszystkich kombinacji takich liczb rośnie wykładniczo wraz ze wzrostem ilości kodów, to myślę, że rozpatrywanie wszystkich kombinacji szybko robiłoby się coraz bardziej kłopotliwe. Można jednak zauważyć, że znaczna większość takich kombinacji daje wyniki o wiele za duże niż chcielibyśmy uzyskać, więc raczej nie ma sensu rozpatrywać ich wszystkich. I ponieważ większość kodów to dość duże liczby rzędu tysięcy lub setek, to w praktyce znaczna większość kombinacji dających wyniki nie większe od 10000 będzie się składać z nie więcej niż 15 różnych wyrazów (i tak pewnie to jest grube przeszacowanie).

No to wróćmy do mojego poprzedniego algorytmu, który wyodrębnił liczby (zbiór C), dla których istnieje w ogóle szansa by złożyć je z pozostałych liczb podzielnych przez 11

c.d:
5) Uporządkujmy pozostałe kody (te podzielne przez 11) w kolejności malejącej. Ich ilość oznaczmy przez M.
6) Teraz po kolei dla każdej z liczb ze zbioru C utwórzmy drzewo, takie, którego korzeń będzie miał wartość równą danemu elementowi ze zbioru C (liczbie którą chcemy uzyskać). Każdy węzeł tego drzewa będzie zawierał maksymalnie M potomków, oraz zawierał informację o aktualnie dodanym kodzie (k), i reszcie jaką należy jeszcze "dołożyć" aby uzyskać szukaną liczbę (r)
7) Poczynając od korzenia twórzmy kolejne węzły w następujący sposób:
a) jeśli wartość reszty r=0, to znaleźliśmy pasującą kombinację (ścieżka od aktualnego węzła do roota)
b) jeśli wartość reszty r<0, to dajemy sobie spokój z tym węzłem i idziemy do kolejnego
c) jeśli r>0, to dodajemy nowe potomki dla aktualnego węzła. Przy czym na nowego potomka rozpatrujemy tylko takie liczby (z puli liczb podzielnych przez 11), których wartość k jest nie większa od r. Wartość reszty takiego potomka r' = r - k.
8) No i tak w kółko...

Sorry za rozwlekły i mało ścisły opis algorytmu, ale jest już dość późno i jestem zmęczony. Mam nadzieje, że ogólny sens jest przejrzysty, lecz jak któryś element jest niejasny to pytaj. Nie daję też gwarancji, ze ten algorytm jest jakoś specjalnie optymalny. Ot przyszedł mi do głowy to go napisałem bez większych rozważań.

Ps. w implementacji można by też zamiast drzew wykorzystać zgrabnie rekurencję co pewnie znacznie uprościłoby kod. Nie chce mi się jednak teraz myśleć co jest tutaj wydajniejsze... wielowskaźnikowe drzewa, czy wielokrotne wywołania rekurencyjne. Mocno by to też pewnie zależało od samej implementacji drzew.

hehehe, czuję się usatysfakcjonowany. bo udało mi się uzyskać z prosty sposób okrągłą liczbę. jest to dziesięć tysięcy. liczby które trzeba dodać to: 333 + 3694 + 2222 + 3751.

hehe, oto kod programu który to umożliwi. kod ma 94 linijki ale może i było można by go napisać prościej i krócej. no nie wiem. ważne że udało się rozwiązać problem.

#include <iostream>
#include <ctime>

int suma=0;
int wartosc_docelowa=0;
int liczba_wylosowana;
int tabl[25];

using namespace std;

int przypisanie_wartosci()
{

    tabl[0]=333;
    tabl[1]= 3509;
    tabl[2]= 440;
    tabl[3]= 1540;
    tabl[4]= 1617;
    tabl[5]= 330;
    tabl[6]= 1320;
    tabl[7]= 220;
    tabl[8]= 1298;
    tabl[9]= 1650;
    tabl[10]= 2035;
    tabl[11]= 2794;
    tabl[12]= 1243;
    tabl[13]= 2772;
    tabl[14]= 3575;
    tabl[15]= 264;
    tabl[16]= 1826;
    tabl[17]= 3311;
    tabl[18]= 440;
    tabl[19]= 3694;
    tabl[20]= 2222;
    tabl[21]= 671;
    tabl[22]= 2233;
    tabl[23]= 3751;
    tabl[24]= 3553;
    return *tabl;
}
bool sprawdzanie()
{
    for(wartosc_docelowa=1000; wartosc_docelowa<=10000; wartosc_docelowa=wartosc_docelowa+1000)
    {
        if(suma == wartosc_docelowa)
        {
            cout<<"Udalo sie! uzyskano liczbe "<<suma;
            return true;
        }
    }
    return false;
}

int main()
{
    przypisanie_wartosci();
    srand(time(NULL));
    int blad,;
    bool zmienna_operacyjna=false;
    do
    {
        suma=333;
        for(int i=0; i<25; i++)
        {
            do
            {
                blad=0;
                liczba_wylosowana=rand()%25;
                for (int j=0; j<25; j++)//sprawdzanie czy sa powtórki
                {
                    if (tabl[j]==tabl[liczba_wylosowana])
                    {
                        blad=1;
                    }
                }
            }
            while (blad==0);
            tabl[ i ]=tabl[liczba_wylosowana];
            cout<<"dodano do "<<suma;
            suma=suma+tabl[liczba_wylosowana];
            cout<<" liczbe "<<tabl[liczba_wylosowana]<<"\n Wynik "<<suma<<"\n\n";
            if(suma>10000)
            {
                cout<<"liczba przekroczyla 10.000!\n\n";
                break;
            }
        zmienna_operacyjna=sprawdzanie();
        }
    }
    while(!zmienna_operacyjna);
    cin.get();
    return 0;
}

programik ten na siłę losuje losową wartość która reprezentuje tablice i dodaje do niej jedną z liczb która nie jest podzielna przez 11, bo to jest klucz. drodzy koledzy nie zauważyliście że żadna z liczb 1000<10000 ; x+1000 nie jest podzielna przez 11? :-P

#include <iostream>
#include <vector>
#define NIESK 999999999
#define PB push_back
using namespace std;


int main()
{
    int n;
    int wart;
    cout << "Podaj liczbe liczb: ";
    cin>>n;
    vector<int> V;
    for(int i=0;i<n;++i)
    {
        cin>>wart;
        V.PB(wart);
    }
    cout << "Podaj liczby do uzyskania(0 konczy program)";
    while(true)
    {
        cin>>wart;
        if(!wart) break;
        vector<int> wynik[wart+1];
        for(int i=0;i<=wart;++i)
             wynik[i].PB(NIESK);
        wynik[0][0]=0;
        for(int i=0;i<V.size();++i)
        {
            for(int j=wart;j>0;j--)
            {
                if(j-V[i]>=0)
                    if(wynik[j-V[i]][0]!=NIESK && wynik[j][0]==NIESK)
                    {
                        wynik[j]=wynik[j-V[i]];
                        wynik[j].PB(V[i]);

                    }
            }
        }
        if(wynik[wart][0]!=NIESK){
        cout << "Liczbe mozna uzyskac z: ";
        for(int i=1;i<(wynik[wart].size()-1);++i)
                cout << wynik[wart][i] << "+";
        cout << wynik[wart][wynik[wart].size()-1] << "=" << wart << endl;
        }
        else
            cout << "Liczby nie mozna uzyskac" << endl;
    }
    return 0;
}

Moje magiczne rozwiązanie :) 8000 też się da uzyskać. Najpierw wpisujesz liczbę tych numerków tzn 25 potem je wrzucasz a potem liczby do sprawdzenia. Rozwiązaniem jak widać był dynamik.

tutaj pojawia sie maly problem
kazda z liczb moze sie powtarzac (mozna miec np 4x po 520, 14 x po 260 etc) o.O!

wiekszosz to wielokrotnosc 260. Trzeba by bylo wykombinowac zeby zakleic "dziure" pomiedzy okraglymi sumami a wielokrotnoscia 260..

Wygląda jak wariant problemu plecakowego… może nadałby się jakiś istniejący algorytm do plecaka.