Dada una array que consiste en el costo de los juguetes. Dado un entero K que representa la cantidad de dinero disponible para comprar juguetes. Escriba un programa para encontrar el número máximo de juguetes que uno puede comprar con la cantidad K.
Nota : Uno puede comprar solo 1 cantidad de un juguete en particular.
Ejemplos:
Input: N = 10, K = 50 cost = { 1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 } Output: 6 Explanation: Toys with amount 1, 5, 9, 10, 12, and 12 can be purchased resulting in a total amount of 49. Hence, maximum number of toys is 6. Input: N = 7, K = 50 cost = { 1, 12, 5, 111, 200, 1000, 10 } Output: 4
La idea para resolver este problema es ordenar primero la array de costos en orden ascendente. Esto ordenará los juguetes en orden creciente de costo. Ahora itere sobre la array de costos y siga calculando la suma de costos hasta que la suma sea menor o igual a K. Finalmente, devuelva la cantidad de juguetes utilizados para calcular la suma que es menor o igual a K.
La siguiente imagen es una ilustración del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to maximize the // number of toys with K amount #include <bits/stdc++.h> using namespace std; // This functions returns the required // number of toys int maximum_toys(int cost[], int N, int K) { int count = 0, sum = 0; // sort the cost array sort(cost, cost + N); for (int i = 0; i < N; i++) { // Check if we can buy ith toy or not if (sum +cost[i] <= K) { sum = sum + cost[i]; // Increment count count++; } } return count; } // Driver Code int main() { int K = 50; int cost[] = { 1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 }; int N = sizeof(cost) / sizeof(cost[0]); cout << maximum_toys(cost, N, K) << endl; return 0; }
Java
// Java Program to maximize the // number of toys with K amount import java.io.*; import java .util.*; class GFG { // This functions returns // the required number of toys static int maximum_toys(int cost[], int N, int K) { int count = 0, sum = 0; // sort the cost array Arrays.sort(cost); for (int i = 0; i < N; i++) { // Check if we can buy ith toy or not if (sum +cost[i] <= K) { sum = sum + cost[i]; // Increment count count++; } } return count; } // Driver Code public static void main (String[] args) { int K = 50; int cost[] = {1, 12, 5, 111, 200, 1000, 10, 9, 12, 15}; int N = cost.length; System.out.print( maximum_toys(cost, N, K)); } } // This code is contributed by anuj_67.
Python3
# Python 3 Program to maximize the # number of toys with K amount # This functions returns the required # number of toys def maximum_toys(cost, N, K): count = 0 sum = 0 # sort the cost array cost.sort(reverse = False) for i in range(0, N, 1): # Check if we can buy ith toy or not if (sum+cost[i] <= K): sum = sum + cost[i] # Increment the count variable count += 1 return count # Driver Code if __name__ == '__main__': K = 50 cost = [1, 12, 5, 111, 200, 1000, 10, 9, 12, 15] N = len(cost) print(maximum_toys(cost, N, K)) # This code is contributed by # Sanjit_Prasad
C#
// C# Program to maximize the // number of toys with K amount using System; class GFG { // This functions returns // the required number of toys static int maximum_toys(int []cost, int N, int K) { int count = 0, sum = 0; // sort the cost array Array.Sort(cost); for (int i = 0; i < N; i++) { // Check if we can buy ith toy or not if (sum +cost[i] <= K) { sum = sum + cost[i]; // Increment count count++; } } return count; } // Driver Code public static void Main () { int K = 50; int []cost = {1, 12, 5, 111, 200, 1000, 10, 9, 12, 15}; int N = cost.Length; Console.Write( maximum_toys(cost, N, K)); } } // This code is contributed by anuj_67.
PHP
<?php // PHP Program to maximize the // number of toys with K amount // This functions returns // the required number of toys function maximum_toys($cost, $N, $K) { $count = 0; $sum = 0; // sort the cost array sort($cost); for ($i = 0; $i < $N; $i++) { // Check if we can buy ith toy or not if ($sum + $cost[$i] <= $K) { $sum = $sum + $cost[$i]; // Increment the count variable $count++; } } return $count; } // Driver Code $K = 50; $cost = array(1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 ); $N = count($cost); echo maximum_toys($cost, $N, $K),"\n"; // This code is contributed by anuj_67 ?>
Javascript
<script> // Javascript Program to maximize the // number of toys with K amount // This functions returns // the required number of toys function maximum_toys(cost, N, K) { let count = 0, sum = 0; // sort the cost array cost.sort(function(a, b){return a - b}); for (let i = 0; i < N; i++) { // Check if we can buy ith toy or not if (sum +cost[i] <= K) { sum = sum + cost[i]; // Increment count count++; } } return count; } let K = 50; let cost = [1, 12, 5, 111, 200, 1000, 10, 9, 12, 15]; let N = cost.length; document.write(maximum_toys(cost, N, K)); </script>
6
Complejidad de tiempo: O(N * logN), donde N es el tamaño de la array de costos.
Publicación traducida automáticamente
Artículo escrito por jaingyayak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA