Dado un entero V y un arreglo arr[] que consta de N enteros, la tarea es encontrar el número máximo de elementos del arreglo que se pueden seleccionar del arreglo arr[] para obtener la suma V. Cada elemento de la array se puede elegir cualquier número de veces. Si no se puede obtener la suma, imprima -1 .
Ejemplos:
Entrada: arr[] = {25, 10, 5}, V = 30
Salida: 6
Explicación:
Para obtener la suma 30, seleccione arr[2] (= 5), 6 veces.
Por lo tanto, la cuenta es 6.Entrada: arr[] = {9, 6, 4, 3}, V = 11
Salida: 3
Explicación:
Para obtener la suma 11, las combinaciones posibles son: 4,4,3
Por lo tanto, la cuenta es 3
Enfoque ingenuo: el enfoque más simple es encontrar recursivamente el número máximo de elementos de array para generar la suma V usando elementos de array de índices 0 a j antes de encontrar el número máximo de elementos necesarios para generar V usando elementos de índices 0 a i donde j < yo < N . Después de completar los pasos anteriores, imprima el recuento de elementos de la array necesarios para obtener la suma V dada .
Complejidad temporal: O(V N )
Espacio auxiliar: O(N)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array table[] de tamaño V + 1 donde table[i] almacenará la solución óptima para obtener sum i .
- Inicialice table[] con -1 y table[0] con 0 ya que se requieren 0 elementos de array para obtener el valor 0 .
- Para cada valor de i = 0 a V , calcule el número máximo de elementos de la array requeridos por la siguiente transición de DP:
table[i] = Max(table[i – arr[j]], table[i]) , Where table[i-arr[j]]!=-1
donde 1 ≤ i ≤ V y 0 ≤ j ≤ N
- Después de completar los pasos anteriores, imprima el valor de la tabla [V], que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that count the maximum
// number of elements to obtain sum V
int maxCount(vector<int> arr, int m, int V)
{
// Stores the maximum number of
// elements required to obtain V
vector<int> table(V + 1);
// Base Case
table[0] = 0;
// Initialize all table values
// as Infinite
for (int i = 1; i <= V; i++)
table[i] = -1;
// Find the max arr required
// for all values from 1 to V
for (int i = 1; i <= V; i++) {
// Go through all arr
// smaller than i
for (int j = 0; j < m; j++) {
// If current coin value
// is less than i
if (arr[j] <= i) {
int sub_res = table[i - arr[j]];
// Update table[i]
if (sub_res != -1 && sub_res + 1 > table[i])
table[i] = sub_res + 1;
}
}
}
// Return the final count
return table[V];
}
// Driver Code
int main()
{
// Given array
vector<int> arr = { 25, 10, 5 };
int m = arr.size();
// Given sum V
int V = 30;
// Function call
cout << (maxCount(arr, m, V));
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function that count the maximum
// number of elements to obtain sum V
static int maxCount(int arr[], int m, int V)
{
// Stores the maximum number of
// elements required to obtain V
int table[] = new int[V + 1];
// Base Case
table[0] = 0;
// Initialize all table values
// as Infinite
for (int i = 1; i <= V; i++)
table[i] = -1;
// Find the max arr required
// for all values from 1 to V
for (int i = 1; i <= V; i++) {
// Go through all arr
// smaller than i
for (int j = 0; j < m; j++) {
// If current coin value
// is less than i
if (arr[j] <= i) {
int sub_res = table[i - arr[j]];
// Update table[i]
if (sub_res != -1
&& sub_res + 1 > table[i])
table[i] = sub_res + 1;
}
}
}
// Return the final count
return table[V];
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 25, 10, 5 };
int m = arr.length;
// Given sum V
int V = 30;
// Function Call
System.out.println(maxCount(arr, m, V));
}
}
Python3
# Python program for the
# above approach
# Function that count
# the maximum number of
# elements to obtain sum V
def maxCount(arr, m, V):
'''
You can assume array elements as domination
which are provided to you in infinite quantity
just like in coin change problem.
I made a small change in logic on coin change
problem (minimum number of coins required).
There we use to take min(table[i-arr[j]]+1,table[i]),
here min is changed with max function.
Dry run:
assume : target = 10, arr = [2,3,5]
table 0 1 2 3 4 5 6 7 8 9 10
0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
taking first domination = 2
table 0 1 2 3 4 5 6 7 8 9 10
0 -1 1 -1 2 -1 3 -1 4 -1 5
taking second domination = 3
table 0 1 2 3 4 5 6 7 8 9 10
0 -1 1 1 2 -1 3 -1 4 3 5
here for i = 6 we have max(table[i-dom]+1,table[i])
hence
=> max(table[6-3]+1,table[6])
=> max(2,3) => 3
taking third domination = 5
table 0 1 2 3 4 5 6 7 8 9 10
0 -1 1 1 2 1 3 -1 4 3 5
Hence total 5 coins are required (2,2,2,2,2)
'''
# Stores the maximum
# number of elements
# required to obtain V
table = [0 for i in range(V+1)]
# Base Case
table[0] = 0
# Initialize all table
# values as Infinite
for i in range(1, V + 1, 1):
table[i] = -1
# Find the max arr required
# for all values from 1 to V
for i in range(1, V + 1, 1):
# Go through all arr
# smaller than i
for j in range(0, m, 1):
# If current coin value
# is less than i
if (arr[j] <= i):
sub_res = table[i - arr[j]]
# Update table[i]
if (sub_res != -1 and
sub_res + 1 > table[i]):
table[i] = sub_res + 1
# Return the final count
return table[V]
# Driver Code
if __name__ == '__main__':
# Given array
arr = [25, 10, 5]
m = len(arr)
# Given sum V
V = 30
# Function Call
print(f'Maximum number of array elements required :
{maxCount(arr, m, V)}')
# This code is contributed by Aaryaman Sharma
C#
// C# program for the
// above approach
using System;
class GFG{
// Function that count the
// maximum number of elements
// to obtain sum V
static int maxCount(int[] arr,
int m, int V)
{
// Stores the maximum number of
// elements required to obtain V
int[] table = new int[V + 1];
// Base Case
table[0] = 0;
// Initialize all table
// values as Infinite
for (int i = 1; i <= V; i++)
table[i] = -1;
// Find the max arr required
// for all values from 1 to V
for (int i = 1; i <= V; i++)
{
// Go through all arr
// smaller than i
for (int j = 0; j < m; j++)
{
// If current coin value
// is less than i
if (arr[j] <= i)
{
int sub_res = table[i - arr[j]];
// Update table[i]
if (sub_res != -1 &&
sub_res + 1 > table[i])
table[i] = sub_res + 1;
}
}
}
// Return the final count
return table[V];
}
// Driver code
static void Main()
{
// Given array
int[] arr = {25, 10, 5};
int m = arr.Length;
// Given sum V
int V = 30;
// Function Call
Console.WriteLine(maxCount(arr,
m, V));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function that count the maximum
// number of elements to obtain sum V
function maxCount(arr, m, V)
{
// Stores the maximum number of
// elements required to obtain V
let table = [];
// Base Case
table[0] = 0;
// Initialize all table values
// as Infinite
for (let i = 1; i <= V; i++)
table[i] = -1;
// Find the max arr required
// for all values from 1 to V
for (let i = 1; i <= V; i++) {
// Go through all arr
// smaller than i
for (let j = 0; j < m; j++) {
// If current coin value
// is less than i
if (arr[j] <= i) {
let sub_res = table[i - arr[j]];
// Update table[i]
if (sub_res != -1
&& sub_res + 1 > table[i])
table[i] = sub_res + 1;
}
}
}
// Return the final count
return table[V];
}
// Driver Code
// Given array
let arr = [ 25, 10, 5 ];
let m = arr.length;
// Given sum V
let V = 30;
// Function Call
document.write(maxCount(arr, m, V));
</script>
6
Complejidad temporal: O(N * V)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryamansharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA