Witam, amino od czasu do czasu organizuje konkurs w ktorym znajdując kupony z [X] pln, i jeżeli uzbieramy (sumując kilka wartosci kuponow) wielokrotność liczby 100, nie większą niż 1000, to możemy odebrać nagrodę. Od razu zapala się żarówka, że można do tego użyć mocy komputera ;p
Więc, program/algorytm powinien sprawdzać, czy nasze kupony dają odpowiednią sumę
Mamy tablicę n-elementową o wartościach 1...999 lub 1000 (nie jestem pewien, lecz nie ma to wielkiego znaczenia)
I teraz. mamy liczby np
12, 58, 120, 54, 15, 73, 523, 972, 16, 212, 2, 107.
I na można dostrzeć m.in takie przykładowe rozwiązania(możliwe, że jest więcej):
120+73+107 = 300
523+120+73+212+58+12+2 = 1000
Nasz algorytm będzie sprawdzał wszystkie możliwe kombinacje sum tego zbioru liczb (np i jeżeli spełnią w/w warunki, to np zwróci "wygrałeś"
I moje pytanie, czy ma ktoś pomysł jak to logicznie poukładać / napisać.
Pojawił się już na forum bardzo podobny program i nawet działa dla w/w parametrów, lecz nie jest zbyt jasny dla mnie ;[
#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.</quote>