skladanie sumy o zadanej wartosci

Witam
potrzebny mi jest program, który będzie dodawał do siebie liczby tak, aby otrzymać z góry założony wynik. Np. do programu wpisuję kilka dowolnych liczb, a jego zadaniem jest dodanie kilku z nich tak (nie koniecznie musi używać wszystkich liczb), żeby wyszedł żądany przeze mnie wynik. Pewnie ciągle to jest nie jasne, więc pokażę to na przykładzie

Chciałbym aby program otrzymał wynik 100.
Podaję mu liczby - 12, 20, 50, 60, 70, 80, 99
Program wysyła na ekran poprawny wynik - 20+80=100
Oczywiście niekiedy rozwiązania będą bardziej skomplikowane, np. będzie musiał użyć 4 liczb żeby uzyskać wynik. Ilość liczb biorących udział w dodawaniu nie jest istotna, ważne żeby każdą wykorzystał raz i dążył do wymaganego wyniku.

Nie mam pojęcia jak się za to zabrać i czy jest to w ogóle możliwe. Macie jakieś pomysły ?

Pozdrawiam :)

Ja bym to próbował zrobić jakimś algorytmem zachłannym brać po kolei liczby najbardziej zbliżone do wyniku i próbować dopasowywać do nich liczby pozostałe, ale raczej to nie jest zbyt optymalne bo złożoność będzie chyba kwadratowa, a zadanie jeszcze się utrudni jak wprowadzimy liczby minusowe :/

tutaj to raczej brutal force.

typedef std::vector<int>::iterator iter;

bool findSum(int sum, iter inputs, iter& output)
{
     if(sum==0)
         return true;

     while(inputs) {
          int a = *inputs++;
          if(a <= sum ) {
               if(findSum(sum-a, inputs, output) {
                     output++ = a;
                     return true;
               }
          }
     }
     return false;
}

Jeśli jesteś kumaty to będziesz wiedział jak to wykorzystać.

Ale co ma być wynikiem? Jakikolwiek podzbiór spełniający założenie? Czy może podzbiór najmniej liczny?
Dla pierwszej opcji próbowałbym zachłannie (co pesymistycznie zamieni się w bruta) a dla opcji drugiej szukałbym dynamicznie (tak jak przy wydawaniu reszty). Obie opcje wymagają posortowania danych.

Shalom napisał(a)

Ale co ma być wynikiem? Jakikolwiek podzbiór spełniający założenie? Czy może podzbiór najmniej liczny?
Dla pierwszej opcji próbowałbym zachłannie (co pesymistycznie zamieni się w bruta) a dla opcji drugiej szukałbym dynamicznie (tak jak przy wydawaniu reszty). Obie opcje wymagają posortowania danych.

wynikiem ma być liczba, konkretna, którą podam albo wpisując ją w kod programu albo już w działający program który zapyta o nią :)

MarekR22 napisał(a)

tutaj to raczej brutal force.
typedef std::vector<int>::iterator iter;

bool findSum(int sum, iter inputs, iter& output)
{
if(sum==0)
return true;

 while(inputs) {
      int a = *inputs++;
      if(a <= sum ) {
           if(findSum(sum-a, inputs, output) {
                 output++ = a;
                 return true;
           }
      }
 }
 return false;

}

Jeśli jesteś kumaty to będziesz wiedział jak to wykorzystać.

dopiero zaczynam programować, ale to co podałeś jest jako tako przejrzyście napisane i się tym pobawię, chociaż wątpię czy jakiś efekt osiągnę. Pozdro Wiślaku ;)

ten problem już był i na pewno powodem jest to.

MarekR22 napisał(a)

ten problem już był i na pewno powodem jest to.

hehe jakbyś zgadł :)

mistico nie zrozumiałeś mnie. Pytałem co ma być wynikiem działania programu ;]
Ale skoro chodzi o ten głupi konkurs to wynikiem mają być wszystkie możliwe kombinacje. W takim razie brute :P Może ew z pewnymi ulepszeniami.

Shalom, to jest nieistotne. Ważne jest to, żeby to działało i znajdowało odpowiedni wynik. Tutaj mam brutala, nie mojego autorstwa, ale są w nim błędy, tzn. nie dodaje tak jak powinien i w ogóle, może Wy wiecie co z nim nie tak ??

#include <iostream>
#include <conio.h>
#include <string>
#include <math.h>
int optymalizacja (int nTab[50])
{
int nSuma=0, i=0, k=1;
do
{
nSuma=nSuma+nTab [i];
++i;
}while ((nSuma<10000) && (i<=50));
for(int j=1;j<i;j++) k = k*2;
std::cout << "Znalazlem tyle niepotrzebnych dodawan (nie będe ich robił: " << k-1 << std::endl;
return k-1;
}
int main()
{
int nTablica [50];
const int nPermutacji=16777215;
std::cout << "Podaj dowolne liczby calkowite: "<<std::endl;
for (int i=0; i<50; ++i) std::cin >> nTablica [i];
std::cout << std::endl;
std::cout << "************************************************* ****" << std::endl;
std::cout << "* podales nastepujace liczby *" << std::endl;
std::cout << "************************************************* ****" << std::endl;
for (int i=0; i<50; ++i)
{
std::cout << nTablica [i] <<"\t";
}
std::cout << std::endl;
int nOptymalizuj=optymalizacja (nTablica);
std::cout << "wyliczono algorytm optymalizacji " << std::endl;
std::cout << "Rozpoczynam dodawanie liczb. czekaj do konca drukowania wynikow! " << std::endl;
std::cout << "nacisnij klawisz"<< std::endl;
getch();
int nRozwiazanie [50];
int nLicznik=0;
for (int i=1+nOptymalizuj; i<=nPermutacji; ++i)
{
int x=i, z=0, y=0, nSumaKontrolna=0;
while (x!=0)
{
if(x%2==0) x=x/2;
else
{
x=(x-1)/2;
nSumaKontrolna=nSumaKontrolna+nTablica [z];
nRozwiazanie [y]=nTablica [z];
++y;
}
++z;
}
if (nSumaKontrolna==10000)// lub ==2000 lub 3000 lub .... lub 10000 tutaj mozna to wstawic.
{
++nLicznik;
for (int j=0; j<y; ++j) std::cout << nRozwiazanie [j]<<"+";
std::cout << "=" << nSumaKontrolna << std::endl;
}
}
std::cout << "Wykonano: " << nPermutacji-nOptymalizuj<< " dodawan liczb ktore podales" << std::endl;
std::cout << "to znaczy o " << nOptymalizuj << " mniej niz zakladano" << std::endl;
std::cout << "Znaleziono: " << nLicznik <<" rozwiazan";
getch();
system ("PAUSE");
return 0;
} 

Nie mogłem się oprzeć ;)
po pierwsze masz znaczniki < cpp >< /cpp > używaj ich, a po drugie formatuj kod! (wcięcia itp.)

Jest to problem NP zupełny.

http://pl.wikipedia.org/wiki/Problem_sumy_podzbioru

__krzysiek85 napisał(a)

Jest to problem NP zupełny.

http://pl.wikipedia.org/wiki/Problem_sumy_podzbioru

więc ?
czy da się to w ogóle zrobić ?

Tak, brute forcem, jak juz wspomniano.