Minimice el número de mochilas con un peso total W necesario para almacenar el conjunto que contiene elementos superiores a W/3

Dada una array , arr[] y el peso W. La tarea es minimizar la cantidad de mochilas necesarias para almacenar todos los elementos de la array. Una sola mochila puede almacenar un peso total máximo de  W.
NOTA: Cada número entero de la array es mayor que (W/3).

Ejemplos:

Entrada: arr[] = {150, 150, 150, 150, 150}, W = 300
Salida: 3
Explicación: Se requiere un mínimo de 3 Mochilas para almacenar todos los elementos
Mochila 1 – {150, 150}, Mochila 2 – {150 , 150}, Mochila 3 – {150}. El peso de cada mochila es <= W.

Entrada: arr[] = {130, 140, 150, 160}, W = 300
Salida: 2
Explicación: Las mochilas se pueden llenar como {130, 150}, {140, 160}.

Enfoque: este problema se puede resolver utilizando el enfoque de dos puntos y la clasificación . Siga los pasos a continuación para resolver el problema dado.

• Ordene la array en orden no decreciente.
• Como la array contiene elementos con valores superiores a W/3 , ninguna mochila puede contener más de dos elementos.
• Mantenga dos punteros L y R . Inicialmente L = 0 , R = N-1 .
• Mantenga un bucle while para los valores L <= R .
• Para cada L y R verifique el valor arr[L] + A[R] <= W . Si esto es cierto entonces es posible poner estos bloques en la misma mochila. Incremente L en 1 y disminuya R en 1 .
• De lo contrario, la mochila tendrá un único elemento de valor arr[i] . Disminuya R en 1 .
• Incremente la respuesta para cada paso válido.

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

// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate
// minimum knapsacks required to
int minimumKnapsacks(int A[], int N, int W)
{
    // Variable to store
    // the knapsacks required
    int ans = 0;
 
    // Maintain two pointers L and R
    int L = 0, R = N - 1;
 
    // Sort the array in
    // non-decreasing order
    sort(A, A + N);
 
    // Maintain a while loop
    while (L <= R) {
 
        // Check if there two elements
        // can be stored in a
        // single knapsack
        if (A[L] + A[R] <= W) {
 
            // Increment the answer
            ans++;
 
            // Decrease the right pointer
            R--;
 
            // Increase the left pointer
            L++;
        }
        else {
            // A single knapsack will be required
            // to store the Right element
            R--;
            ans++;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    int W = 300;
    int arr[] = { 130, 140, 150, 160 };
 
    // To store the size of arr[]
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Print the answer
    cout << minimumKnapsacks(arr, N, W);
}

// Java program for the above approach
import java.util.*;
public class GFG
{
 
// Function to calculate
// minimum knapsacks required to
static int minimumKnapsacks(int A[], int N, int W)
{
   
    // Variable to store
    // the knapsacks required
    int ans = 0;
 
    // Maintain two pointers L and R
    int L = 0, R = N - 1;
 
    // Sort the array in
    // non-decreasing order
    Arrays.sort(A);
 
    // Maintain a while loop
    while (L <= R) {
 
        // Check if there two elements
        // can be stored in a
        // single knapsack
        if (A[L] + A[R] <= W) {
 
            // Increment the answer
            ans++;
 
            // Decrease the right pointer
            R--;
 
            // Increase the left pointer
            L++;
        }
        else {
            // A single knapsack will be required
            // to store the Right element
            R--;
            ans++;
        }
    }
    return ans;
}
 
// Driver code
public static void main (String args[])
{
   
    int W = 300;
    int arr[] = { 130, 140, 150, 160 };
 
    // To store the size of arr[]
    int N = arr.length;
 
    // Print the answer
    System.out.println(minimumKnapsacks(arr, N, W));
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python implementation for the above approach
 
# Function to calculate
# minimum knapsacks required to
def minimumKnapsacks(A, N, W):
    # Variable to store
    # the knapsacks required
    ans = 0;
 
    # Maintain two pointers L and R
    L = 0
    R = N - 1;
 
    # Sort the array in
    # non-decreasing order
    A.sort();
 
    # Maintain a while loop
    while (L <= R):
 
        # Check if there two elements
        # can be stored in a
        # single knapsack
        if (A[L] + A[R] <= W):
 
            # Increment the answer
            ans += 1
 
            # Decrease the right pointer
            R -= 1
 
            # Increase the left pointer
            L += 1
        else:
            # A single knapsack will be required
            # to store the Right element
            R -= 1
            ans += 1
    return ans;
 
 
# Driver Code
 
W = 300;
arr = [ 130, 140, 150, 160 ]
 
# To store the size of arr[]
N = len(arr);
 
# Print the answer
print(minimumKnapsacks(arr, N, W))
 
# This code is contributed by saurabh_jaiswal.

// C# program for the above approach
using System;
public class GFG
{
 
// Function to calculate
// minimum knapsacks required to
static int minimumKnapsacks(int []A, int N, int W)
{
   
    // Variable to store
    // the knapsacks required
    int ans = 0;
 
    // Maintain two pointers L and R
    int L = 0, R = N - 1;
 
    // Sort the array in
    // non-decreasing order
    Array.Sort(A);
 
    // Maintain a while loop
    while (L <= R) {
 
        // Check if there two elements
        // can be stored in a
        // single knapsack
        if (A[L] + A[R] <= W) {
 
            // Increment the answer
            ans++;
 
            // Decrease the right pointer
            R--;
 
            // Increase the left pointer
            L++;
        }
        else {
            // A single knapsack will be required
            // to store the Right element
            R--;
            ans++;
        }
    }
    return ans;
}
 
// Driver code
public static void Main ()
{
   
    int W = 300;
    int []arr = { 130, 140, 150, 160 };
 
    // To store the size of arr[]
    int N = arr.Length;
 
    // Print the answer
    Console.Write(minimumKnapsacks(arr, N, W));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript implementation for the above approach
 
    // Function to calculate
    // minimum knapsacks required to
    const minimumKnapsacks = (A, N, W) => {
     
        // Variable to store
        // the knapsacks required
        let ans = 0;
 
        // Maintain two pointers L and R
        let L = 0, R = N - 1;
 
        // Sort the array in
        // non-decreasing order
        A.sort();
 
        // Maintain a while loop
        while (L <= R) {
 
            // Check if there two elements
            // can be stored in a
            // single knapsack
            if (A[L] + A[R] <= W) {
 
                // Increment the answer
                ans++;
 
                // Decrease the right pointer
                R--;
 
                // Increase the left pointer
                L++;
            }
            else
            {
             
                // A single knapsack will be required
                // to store the Right element
                R--;
                ans++;
            }
        }
        return ans;
    }
 
    // Driver Code
    let W = 300;
    let arr = [130, 140, 150, 160];
 
    // To store the size of arr[]
    let N = arr.length;
 
    // Print the answer
    document.write(minimumKnapsacks(arr, N, W));
 
    // This code is contributed by rakeshsahni
 
</script>

2

Complejidad de tiempo: O(N*log(N)) 
Espacio auxiliar: O(1)