Problema Bancnotelor

Enunț:

Un vânzător trebuie să dea rest unui client o sumă de bani S, având la dispoziție bancnote de valori b1,b2,…,bn în număr nelimitat. Știind că vânzătorul intenționează să folosească un număr cât mai mic de bancnote și că are la dispoziție întotdeauna bancnote de valoare 1, să se afișeze modalitatea optimă de plată a restului.

Indicație de rezolvare:

Vom folosi tabloul unidimensional C cu S+1 componente pentru a salva soluțiile subproblemelor: C[j] reprezintă numărul minim de bancnote de tipul b1,b2,…,bn folosite pentru plata sumei j. Numărul minim de bancnote necesar plății sumei S (soluția optimală a problemei) va fi calculat în C[S]. Dacă pentru plata optimă a sumei j se folosește o bancnotă de tipul bi, atunci numărul de bancnote crește cu o unitate și se reduce corespunzător suma de plată.

Implementare:

 

Cod Sursa C++

// BancnoteDinamicCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
#define dim 500
 
using namespace std;
 
int C[dim], b[dim], n, S, s[dim];
 
int min(int a, int b)
{
	if (a < b)
		return a;
	else
		return b;
}
 
void plataS()
{
	int i, j;
	//tabloul C are S+1 elemente
	C[0] = 0;
	for (j = 1; j <= S; j++)
	{
		C[j] = INT_MAX;
		for (i = 0; i < n;i++)
		if (b[i] <= j && 1 + C[j - b[i]] < C[j])
		{
			C[j] = 1 + C[j - b[i]];
			s[j] = b[i];
		}
	}
	cout << "Numarul minim de bancnote: " << C[S] << endl;
}
 
void constructSol(int j)
{
	if (j > 0)
	{
		constructSol(j - s[j]);
		cout << s[j] << " ";
	}
}
 
int main()
{
	cout << "n= ";
	cin >> n;
	cout << "S= ";
	cin >> S;
	for (int i = 0; i < n; i++)
	{
		cout << "b[" << i << "]=";
		cin >> b[i];
	}
	plataS();
	cout << "Bancnotele selectate: ";
	constructSol(S);
	system("pause");
}

 Rezultat: