Wydawanie reszty. Pomoc w uzupełnieniu.

[MrDynamite12]

Siemka.

Otrzymałem zadanie, aby wydać pewną kwotę w podanych nominałach.

Nominałów ma być jak najmniej. (Oczywista, oczywistość)

Na koniec mam wypisać:

ilość użytych monet(nominałów)

wszystkie użyte monety od podanej kwoty w dół.

 

Np.

Wejście:
3 13
1 2 5
Wyjście
4
5 5 2 1

 

Doszedłem do tego:

#include <cstdio>
int main() {
int N, K; //N liczba nominałów, K żądana kwota
scanf("%d%d", &N, &K); //Wczytujemy ile mamy nominałów[N] i jaką kwotę[K] mamy wydać
int nominal[N], dp[K+1], prev[K+1]; //Definiujemy Tablice.
//Nominal[N] - miejsce na nasze nominały
//dp[K+1] - miejsce na zapisanie najniższych ilości monet.
//prev[K+1] - miejsce na zapisanie poprzedniego nominału, do którego został dodany aktualnie sprawdzany.

dp[0] = 0; //Ustawiamy zakładkę 0 [ilość miejsc] na 0
for (int i = 1; i <= K; i++) { //Rozpoczynamy pętlę. Ustawianie wszystkie na tzw. Nieskończoność.
 dp[i]=10001; }
for (int i = 0; i < N; i++) { //Rozpoczynamy pętlę. Zczytanie z taśmy wszystkich nominałów.
 scanf("%d", &nominal[i]); }
for (int i = 1; i <= N; i++) { //Rozpoczynamy pętlę. Od 1 do Liczba Nominałów(Sprawdzanie każdego nominału).
 for (int y = 0; y <= K-nominal[i]; y++) { //Rozpoczynamy pętlę. Od 0 do Żądanej kwoty - Aktualny nominał(
		 if (dp[y] + 1 < dp[y+nominal[i]]); { //Jeżeli aktualna liczba użytych monet, jest mniejsza od poprzedniej.
			 prev[y+nominal[i]] = nominal[i]; // Zapisujemy poprzednią liczbę, do któej dodaliśmy aktualny nominał.
			 dp[y+nominal[i]] = dp[y]+1; // Zapisujemy aktualną ilość użytych monet.
		 }
 }
printf("%d", dp[K]);
}
}
getchar(); getchar();
return 0;
}

 

Wraz z pomocą cioci wikipedii, oraz komentowania tego co piszę doszedłem dość daleko.

 

Potrzebuję tylko to uzupełnić(poprawić), aby liczyło i wypisywało to, czego potrzebuję

 

P.S. Program jest rąbnięty, gdyż dla przykładowych danych otrzymuję wynik:

100071000410004

 

Dziękuję

 

Edit:

 

Poprawiona wersja kodu, bez komentarzy aby Pan Sopelek się doczytał.

#include <cstdio>
int main() {
    int N, K;
    scanf("%d%d", &N, &K);
    int nominal[N], dp[K+1], prev[K+1];

    dp[0] = 0;
    for (int i = 1; i <= K; i++) {
		    dp[i]=10001; }
    for (int i = 0; i < N; i++) {
		    scanf("%d", &nominal[i]); }
    for (int i = 1; i <= N; i++) {
		    for (int y = 0; y <= K-nominal[i]; y++) {
					   if (dp[y] + 1 < dp[y+nominal[i]]); {
							  prev[y+nominal[i]] = nominal[i];
							  dp[y+nominal[i]] = dp[y]+1;
					   }
		    }
    printf("%d", dp[K]);
  }
    }
    getchar(); getchar();
    return 0;
}

[Sopelek997]

unsigned int waluty[14] = {20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1}; //w groszach, albo sobie sczytaj jak tak chcesz, jak masz rosnąco to w pętli iteruj od końca
unsigned int kwota; //w groszach
int i = 0;
while(kwota)
{
if(kwota>=waluty[i]) kwota-=waluty[i], std::cout << waluty[i] << '\n'; //czy cos w tym wstylu, np wpisujesz do listy
else ++i;
}

twojego kodu nawet nie poprawiam bo sie nie idzie doczytac

mam nadzieję, ze jesteś na tyle ogarnięty, że przerobić to już sobie potrafisz.

Jak nie to albo poczekaj do jutro aż będę miał więcej chęci, albo poczekaj aż ktoś ci to zrobi

[Krycho]

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

// standard c++0x

using namespace std;

typedef istream_iterator<int> in;

int main()
{
int amount,sum;
cin >> amount >> sum;
vector<int>coins;
for(int i(amount);i-->0;)
coins.push_back(*in(cin));
sort(coins.begin(),coins.end(),[](int i,int j){return i>j;});
vector<int>result(amount);
int j(0);
for_each(coins.begin(),coins.end(),[&](int i){while(sum-i>=0){sum-=i;result[j]++;}j++;});
cout << accumulate(result.begin(),result.end(),0) << endl;
j = 0;
for_each(coins.begin(),coins.end(),[&](int i){while(result[j]--){cout << i << " ";}j++;});
return 0;
}

Kompilator musi obslugiwac nowy standard c++11.

 

http://ideone.com/MuoCIt

[MrDynamite12]

Ale z was pały. Nikt się nie domyśli, że mam skorzystać tylko z tych opcji które są podane w moim kodzie(Nie ma tam while'a, lecz jego też mogę użyć). Oraz, że wszystko ma być tylko z <cstdio> nie <iostream> i innych...

 

Sam sobie poradze... Cholera.

 

P.S. Odpowiedź Krycha jest w miarę poprawna(oprócz tego, że użyłeś funkcji których nie znam).

Ale, Sopelek poszedł po całej linii. Nie musisz się wymądrzać i ubliżać innym tylko dlatego, że jesteś na wyższym(więcej umiesz) etapie.

 

Dziękuję panom za pomoc. Skorzystam tylko w pewnym stopniu z pomocy Krycha.

[Sopelek997]

Ale, Sopelek poszedł po całej linii. Nie musisz się wymądrzać i ubliżać innym tylko dlatego, że jesteś na wyższym(więcej umiesz) etapie.

LOL. O co ci chodzi? Czemu się rzucasz od razu? To, że twój kod jest brzydki i zawiera oczywiste komentarze, to nie moja wina. I przyzwyczajaj się, że kodu nie będziesz czytał jedynie ty, więc masz go pisać tak, aby bez komentarzy było wiadomo co się w nim dzieje.

 

btw.

trochę prościej napisane.

#include <iostream>
#include <list>
int main()
{
std::list<size_t> reszta;
size_t n;
size_t kwota;
std::cin >> n;
std::cin >> kwota;
size_t * nominaly = new size_t [n];
size_t i = n;
while(i--)
 std::cin >> nominaly[i];
i = 0;
size_t ilosc_nominalow = 0;
std::list<size_t>::iterator it = reszta.begin();
while(kwota)
{
 if(kwota>=nominaly[i])
 {
	 kwota-=nominaly[i];
	 ++ilosc_nominalow; //można zamiast tego użyć reszta.size() przy wypisywaniu niżej
	 reszta.push_back(nominaly[i]);
	 ++it;
 }
 else ++i;
}
std::cout << ilosc_nominalow << '\n';
for(it = reszta.begin(); it != reszta.end(); ++it)
 std::cout << *it << ' ';
return 0;
}

 

Ale z was pały. Nikt się nie domyśli, że mam skorzystać tylko z tych opcji które są podane w moim kodzie

weź daj sobie na wstrzymanie

[Krycho]

@dynamite

 

Moim zamierzeniem nie byla czytelnosc ani prostota kodu a wrecz odwrotnie. Uzylem specjalnie skomplikowanej skladni, bo problem jest na prawde banalny. Napisales ze chcesz pomocy to ja otrzymales. Moja magiczna wszystkowiedzaca kula niestety jest w naprawie aktualnie i nie, nie domyslilem sie, ze nalezy uzywac jedynie skladni i bibliotek z c. Jesli nie podoba sie ze ktos poswieca swoj czas i pomaga to nikt nie trzyma Cie tu na sile.

[MrDynamite12]

Sopelek, pierwszy się rzuciłeś, że jestem idiotą bo nie umiem pisać... Komentarzy były najpierw dla mnie.

 

Wasze kody mi nie są potrzebne, gdyż użyte są funkcje których nie znam i widać, że ktoś mi pomógł(A raczej zrobił to za mnie).

 

Krycho, dzięki.

[Sopelek997]

Sopelek, pierwszy się rzuciłeś, że jestem idiotą bo nie umiem pisać...

Pokaż, gdzie?

 

Wasze kody mi nie są potrzebne, gdyż użyte są funkcje których nie znam

Więc ucz się na bieżąco, a nie narzekaj, że rozwiązaliśmy problem lepiej.