Colocación de Sudo | Recorrido de colocación

Dada una array A de N enteros positivos y un presupuesto B. Su tarea es decidir la cantidad máxima de elementos que se seleccionarán de la array de modo que el costo acumulado de todos los elementos seleccionados sea menor o igual al presupuesto B. Costo de selección el i-ésimo elemento viene dado por: A[i] + (i * K) donde, K es una constante cuyo valor es igual al número de elementos elegidos. La indexación (i) está basada en 1. Imprime el número máximo y su respectivo costo acumulativo.
Ejemplos: 
 

Entrada : arr[] = { 2, 3, 5 }, B = 11 
Salida : 2 11 
Explicación : Costo de elegir elementos máximos = {2 + (1 * 2) } + {3 + (2 * 2)} = 4 + 7 = 11 (que es igual al presupuesto)
Entrada : arr[] = { 1, 2, 5, 6, 3 }, B = 90 
Salida : 4 54 
 

Requisitos previos : búsqueda binaria
 

Enfoque : La idea aquí es utilizar la búsqueda binaria en todos los valores posibles de K, es decir, el número óptimo de elementos a seleccionar. Comience con cero como límite inferior y termine con el número total de elementos, es decir, N como límite superior. Compruebe si al establecer K como Mid actual , el costo acumulado obtenido es menor o igual al presupuesto. Si cumple la condición, intente aumentar K configurando Start como (Mid + 1) , de lo contrario, intente disminuir K configurando End como (Mid – 1) . 
La verificación de la condición se puede realizar de manera de fuerza bruta simplemente modificando la array de acuerdo con la fórmula dada y agregando los K (número actual de elementos que se seleccionarán) valores modificados más pequeños para obtener el costo acumulativo.
A continuación se muestra la implementación del enfoque anterior. 
 

// 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 false
bool 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 number
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;
 
    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 Code
int 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 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 + "\n");
    }
 
    // 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

# Python Program to find the optimal number of
# elements such that the cumulative value
# should be less than given number
value = 0
 
 
# This function returns true if the value cumulative
# according to received integer K is less than budget
# B, otherwise returns false
def 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 number
def 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 Code
if __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# 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 + "\n");
    }
 
    // 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

<script>
 
// JavaScript Program to find the optimal number of
// elements such that the cumulative value
// should be less than given number
 
 
// This function returns true if the value cumulative
// according to received integer K is less than budget
// B, otherwise returns false
 
let cumulativeValue = 0;
 
function canBeOptimalValue(K, arr, N, B) {
    // Initialize a temporary array which stores
    // the cumulative value of the original array
    let tmp = new Array(N);
 
    for (let i = 0; i < N; i++)
        tmp[i] = (arr[i] + K * (i + 1));
 
    // Sort the array to find the smallest K values
    tmp.sort((a, b) => a - b);
 
    cumulativeValue = 0;
    for (let i = 0; i < K; i++)
        cumulativeValue += tmp[i];
 
    // Check if the value is less than budget
    return cumulativeValue <= B;
}
 
// This function prints the optimal number of elements
// and respective cumulative value which is less than
// the given number
function findNoOfElementsandValue(arr, N, B) {
    let start = 0; // Min Value or lower bound
 
    let end = N; // Max Value or upper bound
 
    // Initialize answer as zero as optimal value
    // may not exists
    let ans = 0;
 
 
 
    while (start <= end) {
        let mid = Math.floor((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, cumulativeValue);
 
    document.write(ans + " " + cumulativeValue + "<br>");
}
 
// Driver Code
 
let arr = [1, 2, 5, 6, 3];
let N = arr.length;
 
// Budget
let B = 90;
findNoOfElementsandValue(arr, N, B);
 
</script>

Producción:  

4 54

Complejidad de tiempo : O(N * (log N) ² ), donde N es el número de elementos en la array dada.