Jakiś czas temu mą uwagę przykuła reklama zupek Amino, bynajmniej nie z powodu ich pysznego smaku, czy oryginalnego podejścia do rekomendacji zupopodobnego produktu firmy Amino. Zaciekawił mnie konkurs... konkurs na pierwszy rzut oka banalny... wystarczy pozbierać kupony i wymienić docelowa kwotę na gotówkę. Niby nic trudnego... ale kwotę którą można wypłacić to wielokrotność tysiąca złotych, nie większa niż 10000. Niby wszystko fajnie, jednak kwoty, które występują w zupkach wcale nie są takie "okrągłe'. Zakładamy, że może być to dowolna liczbą mniejsza niż 10k, czyli jest ich właśnie niespełna 10k. Teraz jeżeli uzbieramy około 10 kuponów, to na pierwszy rzut oka można stwierdzić, czy się wygrało, czy też nie. Gorzej jak jest się zapalonym pożeraczem produktów zakładów chemicznych Amino i ma się tych kuponów więcej. Pojawia się problem: jak mam znaleźć okrągłą kwotę z N kuponów, skoro liczba kombinacji to 2^N. Dla przykładu 56 kuponów to 72057594037927936 kombinacji ;)

Otóż problem z którym się tu spotykamy jest jednym z ważniejszych problemów teorii złożoności i fachowo nazywa się problemem sumy podzbioru. Co gorsza problem ten jest problemem klasy NPC, czyli niedeterministycznie wielomianowy, czyli taki dla którego nie ma rozwiązania dokładnego w czasie wielomianowym. Innymi słowy liczenie na kartce od razy możemy sobie odpuścić.

Ok. w takim razie zaprzęgnijmy do tego komputer. Ale to rodzi kolejny problem: jak w rozsądnym czasie wygenerować wszystkie kombinacje kuponów, spamiętać je i jeszcze zmieścić się w możliwie małej pamięci.

Może po kolei. Zastanówmy się najpierw jak będziemy przechowywać listy kuponów tworzących dane sumy. Samo pytanie wskazuje na użycie listy. Ale nie ma sensu dla każdej sumy tworzyć oddzielnej listy, tylko wystarczy nam taki zabieg: załóżmy, że mamy dwie sumy 16 i 26. 16 składa się z 1,3,4,8; natomiast 26 z tych samych kuponów co 16 oraz kuponu 10, czyli 1,3,4,8,10.
Gdybyśmy zapisywali oddzielnie w tablicy kupony potrzebne do złożenia 16 i 26 potrzebowalibyśmy 9 komórek takiej tablicy:
16 = 1 + 3 + 4 + 8
26 = 1 + 3 + 4 + 8 + 10
Jeżeli natomiast użyjemy listy w sposób następujący:

zużyjemy tylko 5 komórek. I tak też zrobimy.

No to mamy pomysł jak zapamiętywać listę kuponów dla danej sumy. Teraz grubszy temat jak wygenerować wszystkie sumy. Na początek wybierzmy strukturę która by się do tego nadawała. Na pierwszy rzut oka lista nie wydaję się podejściem głupim. Tablica - nie bardzo, bo trzeba by zadeklarować 2^N komórek, bo przecież tyle jest kombinacji... ale po co, przecież zdublowanych sum zapisywać nie będziemy, te powyżej 10000 też na nic na się nie zdadzą. Dla wygody chciałbym też, aby nasza lista sum była posortowana, żeby łatwo można było sumy >10k usuwać. Przy użyciu tablicy będą tylko problemy z utrzymaniem jej porządku. Ok bierzemy listę.

1. Na naszą listę L wpiszmy wartość 0.
2. Jeżeli nie mamy kuponów to wychodzimy z algorytmu, a lista L zawiera wszystkie możliwe sumy.
3. Weźmy jeden kupon i dodajmy do listy L wszystkie elementy z listy L powiększone o wartość kuponu.
4. Wróćmy do punktu 2.

Zamieszane? Wcale nie, mały przykład:
Mamy takie kupony 1, 3, 4, 8, 10
Na początek L = [ 0 ].
Bierzemy pierwszy kupon (1) i dodajemy do listy L (0+1). L = [0,1].
Bierzemy kupon 3, dodajemy do listy (0+3), (1+3). L = [0,1,3,4].
Bierzemy kupon 4, dodajemy (0+4), (1+4), (3+4), (4+4). Ale przecież 4 jest już na liście więc to pomijamy, L = [0,1,3,4,5,7,8]
itd...

Prawda, że proste :) Teraz wystarczy przejrzeć listę L i zobaczyć czy jest na niej jakaś wielokrotność 1000PLN i kasa nasza. Dobrze by było wiedzieć jeszcze z jakich kuponów pozbierać tę okrągłą kwotę. O tym ja za jednym zamachem dodawać kupony do listy i rozszerzać listę o powiększone elementy będzie w komentarzach kodu. No właśnie implementacja... a niech będzie dzisiaj w C, żeby było szybko, a przy okazji sprawdzę czy umiem jeszcze implementować listę :)

#include <stdio.h>
#include <stdlib.h>

// Definicja elementu jednokierunkej listy przechowującej Kupony
typedef struct kupon {
  int value;
  struct kupon * next;
} elKupon;

// Definicja elementu dwukierunkwej listy przechowującej możliwe do utworzenia sumy
typedef struct element {
  int value;
  elKupon * kupon;
  struct element * next;
  struct element * prew;
} elList;

// Tworzy i inicjuje listę sum;
elList * makeList() {
  elList * l;
  l = malloc(sizeof(elList));
  l->value = 0;
  l->kupon = NULL;
  l->next = NULL;
  l->prew = NULL;
  return l;
}

// rozszerza listę o elementy elementy tejże listy powiększone o wartość add
void mergeAddList(elList * list, int add) {
  elList *l,*p,*n;
  elKupon * pk, *nk;
  int nv;
  
  // przyjmujemy tylko wartosci wieksze od zera
  if (add <= 0)
    return;
    
  // kopiujemy wskaznik na liste
  l = list;
  
  // przesuwamy wskaznik na koniec listy
  // przegladamy listę od konca, tj. od elementow najwiekszych
  // aby nowo dodawane elementy lądowaly na liście za rozpatrywaną wartoscia
  // nie potrzeba przez to tworzyć tymczasowej listy dodawanych elementow
  while (l->next != NULL)
    l = l->next;
  
  // kopiujemy wskaznik konca listy do p
  p = l;
    
  // dopuki p wskazuje na jakas wartosc
  // mamy jakies wartosci do powiekszenia i dodania do listy
  while (p != NULL) {
  
    // nowa wartosc do dodania
    nv = p->value + add;
    
    // lista kuponow tworzacych poprzednia wartosc
    nk = p->kupon;
    
    // przesuwamy sie o pozycje wstecz
    // (potrzebne wartosci juz skopiowalismy powyzej)
    p = p->prew;
    
    // jezeli nowa wartosc jest wieksza niz 10000 pomijamy ja
    // amino nie wyplaca takich kwot :)
    if (nv > 10000) 
      continue;
    
    // przesuwamy l wstacz dopuki wartosc na liscie bedzie 
    // mniejsza lub rowna nowej wartosci
    while (l->value > nv)
      l = l->prew;

    // jezeli nowa wartosc jest już na liści pomijamy ją
    if (l->value == nv)
      continue;
    
    // tworzymy nowy element listy z naszą nową wartosci
    n = malloc(sizeof(elList));
    n->value = nv;
    n->prew = l;
    n->next = l->next;
    
    // jeżeli istnieje element wiekszy od dodawanego
    // informujemy go ze ma nowego poprzednika
    if (l->next)
      l->next->prew = n;
      
    // dodajemy nowo utworzony element do listy 
    l->next = n;      
    
    // tworzymy nowy wpis dla kuponu
    pk = malloc(sizeof(elKupon));
    pk->value = add;
    // jaki kolejne elementy listy koponów tworzacych nowo dodana sume
    // stanowi ten kupon i lista skopiowana z p->kupon
    pk->next = nk;
    // dodajemy liste kuponow do nowo dodanej sumy
    n->kupon = pk;
  }
}

int main() {
  int r;  
  elList * list, *t;
  elKupon * pk;
  
  // tworzymy listę zawierajaca jedynie sume wartosci 0 
  list = makeList();
    
  // dopuki mozemy, czytamy ze standardowego wejscia liczby 
  while (scanf("%d", &r) == 1) {
    // rozszerzamy listę elementów o elementy tabliczy list powiekszone o r
    mergeAddList(list, r);
  }
  
  r = 0; // mowi o ty czy coś znaleźlismy
  
  // przegladamy liste
  t = list; 
  while (t) { 
    // jezeli cos nie dzieli sie przez 1000 bez reszty i nie jest 0
    // czyli nie jest wielkokrotnosci tysiaca
    // nie interesuje nas - przechodzimy dalej
    if (t->value % 1000 || t->value == 0) {
      t = t->next;
      continue;
    }
    
    // znalexlismy cos
    r = 1;
    printf("Masz %d PLN złożone z nastepujacych kuponow:\n", t->value);
    
    // wypisjemy kupony
    pk = t->kupon;
    while (pk) {
      printf("\t%d\n", pk->value);
      pk = pk->next;
    }
    
    // przechodzimy do nastepnej sumy
    t=t->next;
  }
  
  // jezeli nic nie znajdziemy - informujemy o tym z zalem 
  if (0 == r)
    printf("Nic jeszcze nie uzbierales :(\n");
  
  // aby było eleganco nalezaloby zwolnić pamiec explicite :)
  // ale system sobie poradzi :)
  
  return 0;
}

okobaka : dobre dobre, jednak z mojego założenia, każda gra losowa lub okazja tego typu jest z góry skazana na straty uczestnika, jednak jeśli chcesz coś wygrać w tego typu konkursie, musisz samemu taki konkurs zorganizować, wtedy wygrana jest gwarantowana :)

sam nie wiem jak tutaj się znalazłem, ah to google
pozdr.