Programowanie zachłanne. Algorytm wydawania reszty:

PROBLEM: Wydaj resztę najmniejszą ilością monet w dostępnych nominałach.

Zapoznaj się z poniższym dokumentem:

lub pobierz go: zachłanny algorytm wydawania reszty

Koduj sam, ale film może Ci pomóc:

W filmie:

• co to jest programowanie zachłanne?
• założenia dp problemu wydawania reszty,
• przygotowanie do kodowania,
• napisanie kodu w C++,
• przykłady uruchomienia w przypadkach optymalnych,
• przykład, w którym metoda zachłanna NIE daje najlepszego wyniku.

Kod napisany w powyższym filmie:

/* Zachłanny algorytm wydawania reszty.
Założenia:
	1) tablica nominałów posortowana MALEJĄCO
	2) ilość każdego nominału NIE jest ograniczona
	3) zawsze jest możliwe wydanie reszty do 0 (ostatni nomimał to 1)
	4) reszta jest liczbą naturalną */
#include <iostream>
#include <string>
using namespace std;
int main(){
	//int nominal[]={6, 4, 1}; // Tablica dostępnych nominałów
	int nominal[]={500, 200, 100, 50, 20, 10, 5, 2, 1}; // Tablica dostępnych nominałów
	int l_nominalow = sizeof(nominal) / sizeof(int); // Ilość elementów tablicy
	int reszta; // Reszta do wydania
	int ilosc = 0; // Łączna ilość "monet" potrzebna do wydania reszty
	int pozycja = 0; // Pozycja aktuanego nominału z tablicy nominałów. Zaczynamy od początku (od największego nominału)
	int i, moneta;
	cout << "dostepne nominaly (monety): \n";
	for(i=0; i<l_nominalow; i++) cout << nominal[i] << " ";
	cout << "\nreszta do wydania: "; cin >> reszta; //Wczytanie wartości reszty do wydania
	cout << endl;
	while(reszta>0){ //Dopóki mamy co wydawać, to wydajemy
		while(nominal[pozycja]>reszta) pozycja++; //Ustalenie największej monety <= od aktualnej reszty
		cout << "aktualna pozycja: " << pozycja;
		moneta=nominal[pozycja]; // Moneta - wartość nominału dla określonej pozycji
		cout << "  moneta: " << moneta;
		cout << "  ilosc monet: " << reszta/moneta; // Ilość monet, które mieszczą się w reszcie
		ilosc=ilosc+reszta/moneta; // Obliczanie łacznej ilości monet potrzebnej do wydania reszty
		reszta=reszta%moneta; // Obliczenie nowej wartości reszty
		cout << "  reszta: " << reszta << endl;	
	}
	cout << "\ncalkowita ilosc potrzebnych monet do wydania reszty: " << ilosc;
	return 0;
}

Wykorzystanie kodów:

• Powyższy kod można wykorzystać w środowisku Dev C++ lub innym. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
• Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh