Keskustelu: Yleinen keskustelu: Matikkapulma

Tarvitsisin seuraavan ongelman kanssa apua:
On satunnainen määrä erikokoisia ryhmiä. Näistä ryhmistä pitäisi yhdistää isompi ryhmä jonka koko yhteensä on vähintään X tai mahdollisimman vähän yli X.

Esim. neljä ryhmää joiden koot ovat 2, 2, 4 ja 6:
jos X = 1: saadaan 2
jos X = 2: saadaan 2
jos X = 3: saadaan 4
jos X = 8: saadaan 2+6=8 tai 2+2+4=8
jos X = 9: saadaan 4+6=10 tai 2+2+6=10

Yritän tehdä ohjelmaa joka palauttaa parhaan yhdistelmän. Sen verran olen jo tuota miettinyt että ahne algoritmi ei ongelmasta suoriudu. Voisiko joku ohjata oikeaan suuntaan ongelman ratkaisussa?

Onko noita erikokoisia ryhmiä miten paljon? Jos niitä on kohtuullinen määrä, niin helpointa olisi varmaan käydä kaikki vaihtoehdot läpi ja palauttaa niistä paras.

edit:
Eli aluksi varmaan ryhmien järjestäminen pienimmästä suurimpaan ja sitten kaikki vaihtoehdot järjestyksessä läpi.

Kaikkien yhdistelmien läpikäyminen ei ole mahdollista koska ryhmiä voi olla pahimmillaan 100 kappaletta, mutta yleensä noin 30.

Edit: voi olla että ongelmaani ei löydy kovin tehokasta ratkaisua. Tarvisin kuitenkin jonkinlaisen ratkaisun joka valitsee noita ryhmiä edes melko järkevästi kohtuullisessa ajassa.

Kuvaamasi ongelma vastaa seuraavaa NP-täydellistä ongelmaa:

http://en.wikipedia.org/wiki/Subset_sum_problem

Ongelmaan ei siis tunneta yleistä tehokasta ratkaisua.

Kuinka suuria luvut voivat olla? Tuossa kerrottu dynaamisen ohjelmoinnin algoritmi toimii hyvin, jos luvut eivät ole kovin suuria.

Antti Laaksonen kirjoitti:

Kuvaamasi ongelma vastaa seuraavaa NP-täydellistä ongelmaa:

http://en.wikipedia.org/wiki/Subset_sum_problem

Ongelmaan ei siis tunneta yleistä tehokasta ratkaisua.

Kuinka suuria luvut voivat olla? Tuossa kerrottu dynaamisen ohjelmoinnin algoritmi toimii hyvin, jos luvut eivät ole kovin suuria.

Tätä hieman pelkäsinkin. Ehkä pitää toteuttaa tuo niin että pienillä määrillä lasketaan oikea ratkaisu ja isoilla määrillä pyritään pääsemään vain lähelle oikeaa ratkaisua.

Tuossa C:llä tehty dynaamisen ohjelmoinnin ratkaisu:

#include <stdio.h>

int n;
int r[100];
int m;
int x;
int d[100][10000];
int p[100][10000];

int main() {
    printf("Montako ryhmää? ");
    scanf("%i", &n);
    printf("Anna ryhmien koot: ");
    for (int i = 0; i < n; i++) {
        scanf("%i", &r[n-i-1]);
        if (r[n-i-1] > m) m = r[n-i-1];
    }
    printf("Anna tavoitekoko: ");
    scanf("%i", &x);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= x+m; j++) {
            if (j-r[i] == 0) {
                d[i][j] = 1;
                p[i][j] = 1;
            } else if (i-1 >= 0 && j-r[i] >= 0 && d[i-1][j-r[i]]) {
                d[i][j] = 1;
                p[i][j] = 1;
            } else if (i-1 >= 0 && d[i-1][j]) {
                d[i][j] = 1;
                p[i][j] = 0;
            }
        }
    }
    for (int i = x; i <= x+m; i++) {
        if (d[n-1][i]) {
            printf("Paras koko: %i\n", i);
            printf("Valittavat ryhmät: ");
            for (int j = n-1; j >= 0; j--) {
                if (p[j][i]) {
                    printf("%i ", r[j]);
                    i -= r[j];
                }
            }
            printf("\n");
            return 0;
        }
    }
    printf("Ei ratkaisua\n");
    return 0;
}

Tämä olettaa, että ryhmiä on enintään 100 ja vastaus on korkeintaan 10000.

Esimerkkisuorituksia:

Montako ryhmää? 4
Anna ryhmien koot: 2 2 4 6
Anna tavoitekoko: 8
Paras koko: 8
Valittavat ryhmät: 2 2 4

Montako ryhmää? 4
Anna ryhmien koot: 2 2 4 6
Anna tavoitekoko: 9
Paras koko: 10
Valittavat ryhmät: 2 2 6

Montako ryhmää? 20
Anna ryhmien koot: 5 12 9 7 10 29 10 23 25 13 6 40 36 6 50 4 22 44 41 39
Anna tavoitekoko: 123
Paras koko: 123
Valittavat ryhmät: 5 12 9 7 10 29 10 25 6 6 4

Kiitoksia! Tuolla algoritmilla saan ongelman laskettua tarpeeksi tehokkaasti.

Hyvä! Huomasin vielä koodissa bugin rivillä 16, mutta korjasin sen nyt aiempaan viestiini.