Orden de índices que es lexicográficamente más pequeño y suma de elementos es <= X

Dada una array arr[] y un entero X , la tarea es encontrar los índices tales que: 
 

1. La suma de los elementos de los índices encontrados es ≤ X
2. El número de índices es el máximo posible.
3. El orden de los índices es lexicográficamente más pequeño, es decir, {0, 0, 1} es lexicográficamente más pequeño que {1, 0, 0}

Tenga en cuenta que cualquier índice se puede elegir más de una vez.
Ejemplos: 
 

Entrada: arr[] = {6, 8, 5, 4, 7}, X = 11 
Salida: 0 2 
La respuesta óptima es [0, 2] ya que lexicográficamente es la más pequeña. 
suma de índices elegidos A[0] + A[2] = 6 + 5 = 11 que es ≤ 11. 
Aquí, [2, 3], [2, 2] o [3, 3] también dan el 
número máximo de índices elegidos índices pero no son lexicográficamente los más pequeños.
Entrada: arr[] = {9, 6, 8, 5, 7, 4}, X = 35 
Salida: 1 3 5 5 5 5 5 5 
 

Enfoque: el problema parece una variación de la programación dinámica, pero resulta que puede resolverse mediante un algoritmo codicioso simple.
Sea m el índice que tiene el primer valor mínimo. Entonces el número máximo de índices realizados es n = X / A[m]. Entonces ans = [m, m, m, …., m], donde el número de m es n, es el orden del número máximo de índices elegidos, con suma total = nx A[m]. También estamos seguros de que la respuesta óptima tiene n valores y no más que eso.
Ahora, podemos obtener un orden lexicográficamente más pequeño con el mismo número de índices elegidos, si podemos encontrar un índice i que sea más pequeño que m tal que podamos reemplazar un índice de valor A[m] por un índice de valor A[i ] sin exceder la suma X, entonces podemos reemplazar el primer elemento en ans por i, haciendo el orden lexicográficamente más pequeño. Para hacerlo lexicográficamente lo más pequeño posible, nos gustaría que el índice i fuera lo más pequeño posible y, luego, nos gustaría usarlo tantas veces como sea posible.
 

Por ejemplo, X = 11, A = [6, 8, 5, 4, 7]. 
El valor mínimo está en el índice 3 y A[3] = 4. Entonces n = 11 / 4 = 2 y ans = [3, 3] con suma total = 4 x 2 = 8. 
Para hacerlo lexicográficamente más pequeño, comprobaremos los índices antes de 3 en orden. 
El primero es 6. Ya que 8 – 4 + 6 = 10 < 11. Hemos encontrado un orden más pequeño [0, 3]. 
Si volvemos a aplicar 6, obtendríamos 10 – 4 + 6 = 12 > 11. Así que continuamos para verificar el siguiente valor de índice 8, que es demasiado grande. Así que seguimos adelante para verificar 5. Dado que 10 – 4 + 5 = 11 <= 11, encontramos un orden más pequeño [0, 2]. Como no queda lugar para el reemplazo, 11 – 11 = 0, nos detenemos aquí. La respuesta final es [0, 2]. 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the chosen indices
vector<int> solve(int X, vector<int>& A)
{
    int min = INT_MAX;
    int ind = -1;
 
    for (int i = 0; i < A.size(); i++) {
        if (A[i] < min) {
            min = A[i];
            ind = i;
        }
    }
 
    // Maximum indices chosen
    int maxIndChosen = X / min;
 
    vector<int> ans;
 
    if (maxIndChosen == 0) {
        return ans;
    }
 
    for (int i = 0; i < maxIndChosen; i++) {
        ans.push_back(ind);
    }
 
    int temp = maxIndChosen;
    int sum = maxIndChosen * A[ind];
 
    // Try to replace the first element in ans by i,
    // making the order lexicographically smaller
    for (int i = 0; i < ind; i++) {
 
        // If no further replacement possible return
        if (sum - X == 0 || temp == 0)
            break;
 
        // If found an index smaller than ind and sum
        // not exceeding X then remove index of smallest
        // value from ans and then add index i to ans
        while ((sum - A[ind] + A[i]) <= X && temp != 0) {
            ans.erase(ans.begin());
            ans.push_back(i);
            temp--;
            sum += (A[i] - A[ind]);
        }
    }
 
    sort(ans.begin(), ans.end());
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> A = { 5, 6, 4, 8 };
    int X = 18;
 
    vector<int> ans = solve(X, A);
 
    // Print the chosen indices
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " ";
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to return the chosen indices
static Vector<Integer> solve(int X, Vector<Integer> A)
{
    int min = Integer.MAX_VALUE;
    int ind = -1;
 
    for (int i = 0; i < A.size(); i++)
    {
        if (A.get(i) < min)
        {
            min = A.get(i);
            ind = i;
        }
    }
 
    // Maximum indices chosen
    int maxIndChosen = X / min;
 
    Vector<Integer> ans = new Vector<>();
 
    if (maxIndChosen == 0)
    {
        return ans;
    }
 
    for (int i = 0; i < maxIndChosen; i++)
    {
        ans.add(ind);
    }
 
    int temp = maxIndChosen;
    int sum = maxIndChosen * A.get(ind);
 
    // Try to replace the first element in ans by i,
    // making the order lexicographically smaller
    for (int i = 0; i < ind; i++) {
 
        // If no further replacement possible return
        if (sum - X == 0 || temp == 0)
            break;
 
        // If found an index smaller than ind and sum
        // not exceeding X then remove index of smallest
        // value from ans and then add index i to ans
        while ((sum - A.get(ind) + A.get(i)) <= X && temp != 0)
        {
            ans.remove(0);
            ans.add(i);
            temp--;
            sum += (A.get(i) - A.get(ind));
        }
    }
 
    Collections.sort(ans);
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    Integer arr[] = { 5, 6, 4, 8 };
    Vector<Integer> A = new Vector<Integer>(Arrays.asList(arr));
    int X = 18;
 
    Vector<Integer> ans = solve(X, A);
 
    // Print the chosen indices
    for (int i = 0; i < ans.size(); i++)
        System.out.print(ans.get(i)+" ");
}
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 implementation of the approach
import sys;
 
# Function to return the chosen indices
def solve(X, A) :
 
    minimum = sys.maxsize;
    ind = -1;
     
    for i in range(len(A)) :
        if (A[i] < minimum ) :
            minimum = A[i];
            ind = i;
     
    # Maximum indices chosen
    maxIndChosen = X // minimum ;
     
    ans = [];
     
    if (maxIndChosen == 0) :
        return ans;
         
    for i in range(maxIndChosen) :
        ans.append(ind);
         
    temp = maxIndChosen;
    sum = maxIndChosen * A[ind];
     
    # Try to replace the first element in ans by i,
    # making the order lexicographically smaller
    for i in range(ind) :
         
        # If no further replacement possible return
        if (sum - X == 0 or temp == 0) :
            break;
             
        # If found an index smaller than ind and sum
        # not exceeding X then remove index of smallest
        # value from ans and then add index i to ans
        while ((sum - A[ind] + A[i]) <= X and temp != 0) :
            del(ans[0]);
            ans.append(i);
            temp -= 1;
            sum += (A[i] - A[ind]);
             
    ans.sort();
    return ans;
 
 
# Driver code
if __name__ == "__main__" :
 
    A = [ 5, 6, 4, 8 ];
    X = 18;
 
    ans = solve(X, A);
 
    # Print the chosen indices
    for i in range(len(ans)) :
        print(ans[i],end= " ");
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
using System.Collections.Generic;
     
class GFG
{
 
// Function to return the chosen indices
static List<int> solve(int X, List<int> A)
{
    int min = int.MaxValue;
    int ind = -1;
 
    for (int i = 0; i < A.Count; i++)
    {
        if (A[i] < min)
        {
            min = A[i];
            ind = i;
        }
    }
 
    // Maximum indices chosen
    int maxIndChosen = X / min;
 
    List<int> ans = new List<int>();
 
    if (maxIndChosen == 0)
    {
        return ans;
    }
 
    for (int i = 0; i < maxIndChosen; i++)
    {
        ans.Add(ind);
    }
 
    int temp = maxIndChosen;
    int sum = maxIndChosen * A[ind];
 
    // Try to replace the first element in ans by i,
    // making the order lexicographically smaller
    for (int i = 0; i < ind; i++)
    {
 
        // If no further replacement possible return
        if (sum - X == 0 || temp == 0)
            break;
 
        // If found an index smaller than ind and sum
        // not exceeding X then remove index of smallest
        // value from ans and then add index i to ans
        while ((sum - A[ind] + A[i]) <= X && temp != 0)
        {
            ans.RemoveAt(0);
            ans.Add(i);
            temp--;
            sum += (A[i] - A[ind]);
        }
    }
 
    ans.Sort();
 
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 5, 6, 4, 8 };
    List<int> A = new List<int>(arr);
    int X = 18;
 
    List<int> ans = solve(X, A);
 
    // Print the chosen indices
    for (int i = 0; i < ans.Count; i++)
        Console.Write(ans[i] + " ");
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the approach
 
// Function to return the chosen indices
function solve(X,A)
{
    let min = Number.MAX_VALUE;
    let ind = -1;
   
    for (let i = 0; i < A.length; i++)
    {
        if (A[i] < min)
        {
            min = A[i];
            ind = i;
        }
    }
   
    // Maximum indices chosen
    let maxIndChosen = Math.floor(X / min);
   
    let ans = [];
   
    if (maxIndChosen == 0)
    {
        return ans;
    }
   
    for (let i = 0; i < maxIndChosen; i++)
    {
        ans.push(ind);
    }
   
    let temp = maxIndChosen;
    let sum = maxIndChosen * A[ind];
   
    // Try to replace the first element in ans by i,
    // making the order lexicographically smaller
    for (let i = 0; i < ind; i++) {
   
        // If no further replacement possible return
        if (sum - X == 0 || temp == 0)
            break;
   
        // If found an index smaller than ind and sum
        // not exceeding X then remove index of smallest
        // value from ans and then add index i to ans
        while ((sum - A[ind] + A[i]) <= X && temp != 0)
        {
            ans.shift();
            ans.push(i);
            temp--;
            sum += (A[i] - A[ind]);
        }
    }
   
    ans.sort(function(a,b){return a-b;});
   
    return ans;
}
 
// Driver code
let A = [5, 6, 4, 8];
let X = 18;
let ans = solve(X, A);
 
// Print the chosen indices
for (let i = 0; i < ans.length; i++)
    document.write(ans[i]+" ");
 
// This code is contributed by rag2127
</script>

0 0 2 2

Complejidad de tiempo: O(NLog(N))