Dado un entero X y una array arr[] de longitud N que consta de enteros positivos, la tarea es elegir el número mínimo de enteros de la array de modo que sumen N . Cualquier número se puede elegir un número infinito de veces. Si no existe una respuesta, imprima -1 .
Ejemplos:
Entrada: X = 7, arr[] = {3, 5, 4}
Salida: 2
El número mínimo de elementos será 2 ya que
se pueden seleccionar 3 y 4 para llegar a 7.Entrada: X = 4, arr[] = {5}
Salida: -1
Enfoque: Ya hemos visto cómo resolver este problema utilizando el enfoque de programación dinámica en este artículo .
Aquí, veremos un enfoque ligeramente diferente para resolver este problema usando BFS .
Antes de eso, avancemos y definamos un estado. Un estado S X se puede definir como el número mínimo de enteros que necesitaríamos tomar de una array para obtener un total de X .
Ahora, si comenzamos a ver cada estado como un Node en un gráfico tal que cada Node está conectado a (S X – arr[0] , S X – arr[1] , … S X – arr[N – 1] ) .
Por lo tanto, tenemos que encontrar el camino más corto desde el estado Na 0 en un no ponderado y esto se puede hacer usando BFS. BFS funciona aquí porque el gráfico no está ponderado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of integers required
int minNumbers(int x, int* arr, int n)
{
// Queue for BFS
queue<int> q;
// Base value in queue
q.push(x);
// Boolean array to check if a number has been
// visited before
unordered_set<int> v;
// Variable to store depth of BFS
int d = 0;
// BFS algorithm
while (q.size()) {
// Size of queue
int s = q.size();
while (s--) {
// Front most element of the queue
int c = q.front();
// Base case
if (!c)
return d;
q.pop();
if (v.find(c) != v.end() or c < 0)
continue;
// Setting current state as visited
v.insert(c);
// Pushing the required states in queue
for (int i = 0; i < n; i++)
q.push(c - arr[i]);
}
d++;
}
// If no possible solution
return -1;
}
// Driver code
int main()
{
int arr[] = { 3, 3, 4 };
int n = sizeof(arr) / sizeof(int);
int x = 7;
cout << minNumbers(x, arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the minimum number
// of integers required
static int minNumbers(int x, int []arr, int n)
{
// Queue for BFS
Queue<Integer> q = new LinkedList<>();
// Base value in queue
q.add(x);
// Boolean array to check if
// a number has been visited before
HashSet<Integer> v = new HashSet<Integer>();
// Variable to store depth of BFS
int d = 0;
// BFS algorithm
while (q.size() > 0)
{
// Size of queue
int s = q.size();
while (s-- > 0)
{
// Front most element of the queue
int c = q.peek();
// Base case
if (c == 0)
return d;
q.remove();
if (v.contains(c) || c < 0)
continue;
// Setting current state as visited
v.add(c);
// Pushing the required states in queue
for (int i = 0; i < n; i++)
q.add(c - arr[i]);
}
d++;
}
// If no possible solution
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 3, 4 };
int n = arr.length;
int x = 7;
System.out.println(minNumbers(x, arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to find the minimum number # of integers required def minNumbers(x, arr, n) : q = [] # Base value in queue q.append(x) v = set([]) d = 0 while (len(q) > 0) : s = len(q) while (s) : s -= 1 c = q[0] #print(q) if (c == 0) : return d q.pop(0) if ((c in v) or c < 0) : continue # Setting current state as visited v.add(c) # Pushing the required states in queue for i in range(n) : q.append(c - arr[i]) d += 1 #print() #print(d,c) # If no possible solution return -1 arr = [ 1, 4,6 ] n = len(arr) x = 20 print(minNumbers(x, arr, n)) # This code is contributed by divyeshrabadiya07 # Improved by nishant.k108
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum number
// of integers required
static int minNumbers(int x, int []arr, int n)
{
// Queue for BFS
Queue<int> q = new Queue<int>();
// Base value in queue
q.Enqueue(x);
// Boolean array to check if
// a number has been visited before
HashSet<int> v = new HashSet<int>();
// Variable to store depth of BFS
int d = 0;
// BFS algorithm
while (q.Count > 0)
{
// Size of queue
int s = q.Count;
while (s-- > 0)
{
// Front most element of the queue
int c = q.Peek();
// Base case
if (c == 0)
return d;
q.Dequeue();
if (v.Contains(c) || c < 0)
continue;
// Setting current state as visited
v.Add(c);
// Pushing the required states in queue
for (int i = 0; i < n; i++)
q.Enqueue(c - arr[i]);
}
d++;
}
// If no possible solution
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 3, 3, 4 };
int n = arr.Length;
int x = 7;
Console.WriteLine(minNumbers(x, arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to find the minimum number
// of integers required
function minNumbers(x, arr, n)
{
// Queue for BFS
var q = [];
// Base value in queue
q.push(x);
// Boolean array to check if a number has been
// visited before
var v = new Set();
// Variable to store depth of BFS
var d = 0;
// BFS algorithm
while (q.length!=0) {
// Size of queue
var s = q.length;
while (s--) {
// Front most element of the queue
var c = q[0];
// Base case
if (!c)
return d;
q.shift();
if (v.has(c) || c < 0)
continue;
// Setting current state as visited
v.add(c);
// Pushing the required states in queue
for (var i = 0; i < n; i++)
q.push(c - arr[i]);
}
d++;
}
// If no possible solution
return -1;
}
// Driver code
var arr = [3, 3, 4];
var n = arr.length;
var x = 7;
document.write(minNumbers(x, arr, n));
// This code is contributed by rrrtnx.
</script>
2
Complejidad temporal: O(N * X)
Espacio Auxiliar: O(N), ya que se ha ocupado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA