Размещение Судо | Тур по размещению
Дан массив A из N положительных целых чисел и бюджет B. Ваша задача состоит в том, чтобы определить максимальное количество элементов, которые должны быть выбраны из массива, так чтобы совокупная стоимость всех выбранных элементов была меньше или равна бюджету B. Стоимость выбора i-й элемент задается следующим образом: A [i] + (i * K), где K - константа, значение которой равно количеству выбранных элементов. Индексация (i) основана на 1. Выведите максимальное число и соответствующую совокупную стоимость.
Примеры:
Input : arr[] = { 2, 3, 5 }, B = 11
Output : 2 11
Explanation : Cost of picking maximum elements = {2 + (1 * 2) } + {3 + (2 * 2)} = 4 + 7 = 11 (which is equal to budget)Input : arr[] = { 1, 2, 5, 6, 3 }, B = 90
Output : 4 54
Предварительные требования : двоичный поиск
Подход : Идея состоит в том, чтобы использовать бинарный поиск по всем возможным значениям K, т. Е. Оптимальному количеству выбираемых элементов. Начните с нуля как нижнюю границу и Конец с общим количеством элементов, т.е. N как верхнюю границу. Убедитесь, что, установив K как текущую среднюю , полученная совокупная стоимость меньше или равна бюджету. Если он удовлетворяет условию, попробуйте увеличить K, установив Start как (Mid + 1) , в противном случае попробуйте уменьшить K, установив End как (Mid - 1) .
Проверка условия может выполняться методом грубой силы, просто изменяя массив в соответствии с заданной формулой и добавляя K (текущее количество выбираемых элементов) наименьших измененных значений, чтобы получить совокупную стоимость.
Below is the implementation of above approach.
C++
// CPP Program to find the optimal number of// elements such that the cumulative value// should be less than given number#include <bits/stdc++.h> using namespace std; // This function returns true if the value cumulative// according to received integer K is less than budget// B, otherwise returns falsebool canBeOptimalValue(int K, int arr[], int N, int B, int& value){ // Initialize a temporary array which stores // the cumulative value of the original array int tmp[N]; for (int i = 0; i < N; i++) tmp[i] = (arr[i] + K * (i + 1)); // Sort the array to find the smallest K values sort(tmp, tmp + N); value = 0; for (int i = 0; i < K; i++) value += tmp[i]; // Check if the value is less than budget return value <= B;} // This function prints the optimal number of elements// and respective cumulative value which is less than// the given numbervoid findNoOfElementsandValue(int arr[], int N, int B){ int start = 0; // Min Value or lower bound int end = N; // Max Value or upper bound // Initialize answer as zero as optimal value // may not exists int ans = 0; int cumulativeValue = 0; while (start <= end) { int mid = (start + end) / 2; // If the current Mid Value is an optimal // value, then try to maximize it if (canBeOptimalValue(mid, arr, N, B, cumulativeValue)) { ans = mid; start = mid + 1; } else end = mid - 1; } // Call Again to set the corresponding cumulative // value for the optimal ans canBeOptimalValue(ans, arr, N, B, cumulativeValue); cout << ans << " " << cumulativeValue << endl;} // Driver Codeint main(){ int arr[] = { 1, 2, 5, 6, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Budget int B = 90; findNoOfElementsandValue(arr, N, B); return 0;} |
Java
// Java Program to find the optimal number of // elements such that the cumulative value // should be less than given number import java.util.*; class GFG { static int value; // This function returns true if // the value cumulative according to // received integer K is less than // budget B, otherwise returns false static boolean canBeOptimalValue(int K, int arr[], int N, int B) { // Initialize a temporary array // which stores the cumulative value // of the original array int[] tmp = new int[N]; for (int i = 0; i < N; i++) tmp[i] = (arr[i] + K * (i + 1)); // Sort the array to find the // smallest K values Arrays.sort(tmp); value = 0; for (int i = 0; i < K; i++) value += tmp[i]; // Check if the value is less than budget return value <= B; } // This function prints the optimal number // of elements and respective cumulative value // which is less than the given number static void findNoOfElementsandValue(int arr[], int N, int B) { int start = 0; // Min Value or lower bound int end = N; // Max Value or upper bound // Initialize answer as zero as // optimal value may not exists int ans = 0; value = 0; while (start <= end) { int mid = (start + end) / 2; // If the current Mid Value is an optimal // value, then try to maximize it if (canBeOptimalValue(mid, arr, N, B)) { ans = mid; start = mid + 1; } else end = mid - 1; } // Call Again to set the corresponding // cumulative value for the optimal ans canBeOptimalValue(ans, arr, N, B); System.out.print(ans + " " + value + "
"); } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 5, 6, 3 }; int N = arr.length; // Budget int B = 90; findNoOfElementsandValue(arr, N, B); }} // This code is contributed by 29AjayKumar |
Python3
# Python Program to find the optimal number of# elements such that the cumulative value# should be less than given numbervalue = 0 # This function returns true if the value cumulative# according to received integer K is less than budget# B, otherwise returns falsedef canBeOptimalValue(K: int, arr: list, N: int, B: int) -> bool: global value # Initialize a temporary array which stores # the cumulative value of the original array tmp = [0] * N for i in range(N): tmp[i] = (arr[i] + K * (i + 1)) # Sort the array to find the smallest K values tmp.sort() value = 0 for i in range(K): value += tmp[i] # Check if the value is less than budget return value <= B # This function prints the optimal number of elements# and respective cumulative value which is less than# the given numberdef findNoOfElementsandValue(arr: list, N: int, B: int): global value start = 0 # Min Value or lower bound end = N # Max Value or upper bound # Initialize answer as zero as optimal value # may not exists ans = 0 value = 0 while start <= end: mid = (start + end) // 2 # If the current Mid Value is an optimal # value, then try to maximize it if canBeOptimalValue(mid, arr, N, B): ans = mid start = mid + 1 else: end = mid - 1 # Call Again to set the corresponding cumulative # value for the optimal ans canBeOptimalValue(ans, arr, N, B) print(ans, value) # Driver Codeif __name__ == "__main__": arr = [1, 2, 5, 6, 3] N = len(arr) # Budget B = 90 findNoOfElementsandValue(arr, N, B) # This code is contributed by# sanjeev2552 |
C#
// C# Program to find the optimal number of // elements such that the cumulative value // should be less than given number using System; class GFG { static int value; // This function returns true if // the value cumulative according to // received integer K is less than // budget B, otherwise returns false static bool canBeOptimalValue(int K, int []arr, int N, int B) { // Initialize a temporary array // which stores the cumulative value // of the original array int[] tmp = new int[N]; for (int i = 0; i < N; i++) tmp[i] = (arr[i] + K * (i + 1)); // Sort the array to find the // smallest K values Array.Sort(tmp); value = 0; for (int i = 0; i < K; i++) value += tmp[i]; // Check if the value is less than budget return value <= B; } // This function prints the optimal number // of elements and respective cumulative value // which is less than the given number static void findNoOfElementsandValue(int []arr, int N, int B) { int start = 0; // Min Value or lower bound int end = N; // Max Value or upper bound // Initialize answer as zero as // optimal value may not exists int ans = 0; value = 0; while (start <= end) { int mid = (start + end) / 2; // If the current Mid Value is an optimal // value, then try to maximize it if (canBeOptimalValue(mid, arr, N, B)) { ans = mid; start = mid + 1; } else end = mid - 1; } // Call Again to set the corresponding // cumulative value for the optimal ans canBeOptimalValue(ans, arr, N, B); Console.Write(ans + " " + value + "
"); } // Driver Code public static void Main(String[] args) { int []arr = { 1, 2, 5, 6, 3 }; int N = arr.Length; // Budget int B = 90; findNoOfElementsandValue(arr, N, B); }} // This code is contributed by Rajput-Ji |
Выход:
4 54
Сложность времени : O (N * (log N) 2 ), где N - количество элементов в данном массиве.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.