Problema Bancnotelor

Problemă:

Să se afișeze toate modalitățile de a plăti o sumă n cu bancnote de valori b1, b2, …, bm. Se
presupune că există un număr suficient de bancnote de fiecare fel.

Indicație de rezolvare:

O soluție va fi sub forma unui vector x, cu x[k] = numărul de bancnote de tipul b[k] care se vor lua. Astfel, suma n se partiționează în mai multe sume, de forma x[k]×b[k]. Deoarece numărul de tipuri de bancnote este limitat la m, va trebui ca să se țină cont de acest
lucru atunci când se trece la atribuirea unei noi valori pentru fiecare x[k].

Implementare:

Cod Sursa VB

Module Module1
    Dim x(51) As String
    Dim b(51) As String
    Dim m(51) As String
    Dim k, n, nsol As Integer
    Dim buna As Boolean
    Dim s As Integer 'suma de plata
 
    Function ConditiiContinuare(ByVal k As Integer)
        Dim suma_partiala As Integer
        suma_partiala = 0
        For i = 1 To k
            suma_partiala = suma_partiala + b(i) * x(i)
        Next i
        If (k < n) Then
            Return suma_partiala <= s
        Else
            Return suma_partiala = s
        End If
    End Function
 
    Sub ScrieSolutia()
        nsol = nsol + 1
        Console.WriteLine("Solutia " & nsol & "este ")
        For i = 1 To n
            Console.WriteLine("Luati " & x(i) & " bancnote de valoare " & b(i))
        Next i
        Console.ReadLine()
    End Sub
 
    Sub Main()
        Console.WriteLine("Problema bancomatului")
        Console.WriteLine("Dati suma de plata ")
        s = Convert.ToInt32(Console.ReadLine())
        Console.WriteLine("Dati numarul de tipuri de bancnote: ")
        n = Convert.ToInt32(Console.ReadLine())
        For i = 1 To n
            Console.WriteLine("Bancnotele de tipul " & i)
            Console.Write(" -valoare: ")
            b(i) = Convert.ToInt32(Console.ReadLine())
            Console.Write(" -nr bucati ")
            m(i) = Convert.ToInt32(Console.ReadLine())
        Next i
        k = 1
        x(k) = -1
        nsol = 0
        While (k > 0)
            buna = False
            While (Not buna And x(k) < m(k))
                x(k) = x(k) + 1
                If (ConditiiContinuare(k)) Then
                    buna = True
                End If
            End While
 
            If (buna) Then
                If (k = n) Then
                    ScrieSolutia()
                Else
                    k = k + 1
                    x(k) = -1
                End If
            Else
                k = k - 1
            End If
        End While
    End Sub
 
End Module

Cod Sursa C++

// BancnoteCPP.cpp : Defines the entry point for the console application.
 
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int x[51], b[51], m[51];
int k, n, nsol;
bool buna;
int S; // suma de plata
 
bool ConditiiContinuare(int k) //!!!
{
	 int suma_partiala=0;
	 for (int i=1; i<=k; i++)
		 suma_partiala+=b[i]*x[i];
	 if (k<n) return suma_partiala<=S;
	 else return suma_partiala==S;
}
 
void ScrieSolutia() //!!!
{
	 nsol++;
	 cout<<"Solutie "<<nsol<<" este:\n";
	 for (int i=1; i<=n; i++)
		 cout<<"  Luati "<<x[i]<<" bancnote de valoare "<<b[i]<<"\n";
	 cout<<"\n";
	 system("pause");
	 getchar();
}
 
int main()
{
	cout<<"Problema bancomatului\n";
	cout<<"Dati suma de plata:"; cin>>S;
	cout<<"Dati numarul n: "; cin>>n;
	for (int i=1; i<=n; i++)
		{
		  cout<<"Bancnotele de tipul "<<i<<":\n";
		  cout<<"  - valoare   : "; cin>>b[i];
		  cout<<"  - nr. bucati: "; cin>>m[i];
		}
	k=1; 
	x[k]=-1; // !!!
	nsol=0; 
	while (k>0) 
	  {
		  buna=false; 
		  while (!buna && x[k]<m[k]) // !!!
				{
					x[k]++; 
					if (ConditiiContinuare(k)) buna=true;
				  
				}
		  if (buna) 
			 if (k==n) 
				 ScrieSolutia(); 
			 else 
				  {
					k++; 
					x[k]=-1; // !!!
				  }
		  else
			  k--;
	  }          
}

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace BancnoteCS
{
    class Program
    {
        static bool ConditiiContinuare(int[]x, int[]b, int n, int k, int s)
        {
            int suma_partiala = 0;
            suma_partiala = 0;
            for (int i = 1; i <= k; i++)
            {
                suma_partiala = suma_partiala + b[i] * x[i];
            }
            if ((k < n))
            {
                return suma_partiala <= s;
            }
            else
            {
                return suma_partiala == s;
            }
        }
 
        static void ScrieSolutia(int[] x, int[]b, int n, int nsol)
        {
            nsol = nsol + 1;
            Console.WriteLine("Solutia " + nsol + " este ");
            for (int i = 1; i <= n; i++)
            {
                Console.WriteLine("Luati " + x[i] + " bancnote de valoare " + b[i]);
            }
            Console.ReadLine();
        }
 
        static void Main(string[] args)
        {
            int k;
            int n;
            int nsol;
            bool buna;
            int[] x = new int[52];
            int[] b = new int[52];
            int[] m = new int[52];
            //suma de plata
            int s;
 
            Console.WriteLine("Problema bancomatului");
            Console.WriteLine("Dati suma de plata ");
            s = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Dati numarul de tipuri de bancnote: ");
            n = Convert.ToInt32(Console.ReadLine());
            for (int i = 1; i <= n; i++)
            {
                Console.WriteLine("Bancnotele de tipul " + i);
                Console.Write(" -valoare: ");
                b[i] = Convert.ToInt32(Console.ReadLine());
                Console.Write(" -nr bucati ");
                m[i] = Convert.ToInt32(Console.ReadLine());
            }
            k = 1;
            x[k] = -1;
            nsol = 0;
            while ((k > 0))
            {
                buna = false;
                while ((!buna & x[k] < m[k]))
                {
                    x[k] = x[k] + 1;
                    if ((ConditiiContinuare(x,b,n,k,s)))
                    {
                        buna = true;
                    }
                }
 
                if ((buna))
                {
                    if ((k == n))
                    {
                        ScrieSolutia(x,b,n,nsol);
                    }
                    else
                    {
                        k = k + 1;
                        x[k] = -1;
                    }
                }
                else
                {
                    k = k - 1;
                }
            }
        }
 
    }
}

Rezultat: