Mover la escala de ponderación alternativa bajo las restricciones dadas

Dada una escala de ponderación y una array de diferentes pesos positivos donde tenemos un suministro infinito de cada peso. Nuestra tarea es poner pesos en los platillos de la balanza izquierda y derecha uno por uno de tal manera que los platillos se muevan hacia el lado donde se coloca el peso, es decir, cada vez, los platillos de la balanza se mueven a lados alternos.

• Nos dan otros ‘pasos’ enteros, tiempos que necesitamos para realizar esta operación.
• Otra restricción es que no podemos poner el mismo peso consecutivamente, es decir, si se toma el peso w, entonces en el siguiente paso, mientras se coloca el peso en el plato opuesto, no podemos tomar w nuevamente.

Ejemplos:

Let weight array is [7, 11]  and steps = 3 
then 7, 11, 7 is the sequence in which 
weights should be kept in order to move
scale alternatively.

Let another weight array is [2, 3, 5, 6] 
and steps = 10 then, 3, 2, 3, 5, 6, 5, 3, 
2, 3 is the sequence in which weights should
be kept in order to move scale alternatively.

Este problema se puede resolver haciendo DFS entre estados de escala.

1. Atravesamos varios estados de DFS para encontrar la solución en la que cada estado de DFS corresponderá al valor de diferencia real entre las bandejas izquierda y derecha y el recuento de pasos actual.
2. En lugar de almacenar los pesos de ambas bandejas, solo almacenamos el valor residual de diferencia y cada vez que el valor de peso elegido debe ser mayor que esta diferencia y no debe ser igual al valor de peso elegido previamente.
3. Si es así, llamamos al método DFS recursivamente con un nuevo valor de diferencia y un paso más.

Consulte el código a continuación para una mejor comprensión,

// C++ program to print weights for alternating
// the weighting scale
#include <bits/stdc++.h>
using namespace std;
  
// DFS method to traverse among states of weighting scales
bool dfs(int residue, int curStep, int wt[], int arr[],
         int N, int steps)
{
    // If we reach to more than required steps,
    // return true
    if (curStep > steps)
        return true;
  
    // Try all possible weights and choose one which
    // returns 1 afterwards
    for (int i = 0; i < N; i++)
    {
        /* Try this weight only if it is greater than
           current residueand not same as previous chosen
           weight */
        if (arr[i] > residue && arr[i] != wt[curStep - 1])
        {
            // assign this weight to array and recur for
            // next state
            wt[curStep] = arr[i];
            if (dfs(arr[i] - residue, curStep + 1, wt,
                    arr, N, steps))
                return true;
        }
    }
  
    //    if any weight is not possible, return false
    return false;
}
  
// method prints weights for alternating scale and if
// not possible prints 'not possible'
void printWeightsOnScale(int arr[], int N, int steps)
{
    int wt[steps];
  
    // call dfs with current residue as 0 and current
    // steps as 0
    if (dfs(0, 0, wt, arr, N, steps))
    {
        for (int i = 0; i < steps; i++)
            cout << wt[i] << " ";
        cout << endl;
    }
    else
        cout << "Not possible\n";
}
  
//    Driver code to test above methods
int main()
{
    int arr[] = {2, 3, 5, 6};
    int N = sizeof(arr) / sizeof(int);
  
    int steps = 10;
    printWeightsOnScale(arr, N, steps);
    return 0;
}

// Java program to print weights for alternating 
// the weighting scale
class GFG 
{
  
    // DFS method to traverse among 
    // states of weighting scales
    static boolean dfs(int residue, int curStep, 
                       int[] wt, int[] arr,
                       int N, int steps) 
    {
  
        // If we reach to more than required steps,
        // return true
        if (curStep >= steps)
            return true;
  
        // Try all possible weights and 
        // choose one which returns 1 afterwards
        for (int i = 0; i < N; i++) 
        {
  
            /*
            * Try this weight only if it is 
            * greater than current residue 
            * and not same as previous chosen weight
            */
            if (curStep - 1 < 0 || 
               (arr[i] > residue &&
                arr[i] != wt[curStep - 1]))
            {
  
                // assign this weight to array and 
                // recur for next state
                wt[curStep] = arr[i];
                if (dfs(arr[i] - residue, curStep + 1,
                                   wt, arr, N, steps))
                    return true;
            }
        }
  
        // if any weight is not possible,
        // return false
        return false;
    }
  
    // method prints weights for alternating scale 
    // and if not possible prints 'not possible'
    static void printWeightOnScale(int[] arr, 
                                   int N, int steps) 
    {
        int[] wt = new int[steps];
  
        // call dfs with current residue as 0 
        // and current steps as 0
        if (dfs(0, 0, wt, arr, N, steps)) 
        {
            for (int i = 0; i < steps; i++)
                System.out.print(wt[i] + " ");
            System.out.println();
        } 
        else
            System.out.println("Not Possible");
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 2, 3, 5, 6 };
        int N = arr.length;
        int steps = 10;
        printWeightOnScale(arr, N, steps);
    }
}
  
// This code is contributed by
// sanjeev2552

# Python3 program to print weights for  
# alternating the weighting scale 
  
# DFS method to traverse among states 
# of weighting scales 
def dfs(residue, curStep, wt, arr, N, steps):
      
    # If we reach to more than required 
    # steps, return true 
    if (curStep >= steps): 
        return True
  
    # Try all possible weights and choose 
    # one which returns 1 afterwards
    for i in range(N):
          
        # Try this weight only if it is greater 
        # than current residueand not same as 
        # previous chosen weight 
        if (arr[i] > residue and 
            arr[i] != wt[curStep - 1]):
              
            # assign this weight to array and 
            # recur for next state 
            wt[curStep] = arr[i] 
            if (dfs(arr[i] - residue, curStep + 1,
                              wt, arr, N, steps)): 
                return True
  
    # if any weight is not possible,
    # return false 
    return False
  
# method prints weights for alternating scale 
# and if not possible prints 'not possible' 
def printWeightsOnScale(arr, N, steps):
    wt = [0] * (steps) 
  
    # call dfs with current residue as 0 
    # and current steps as 0 
    if (dfs(0, 0, wt, arr, N, steps)):
        for i in range(steps):
            print(wt[i], end = " ")
    else:
        print("Not possible")
  
# Driver Code
if __name__ == '__main__':
  
    arr = [2, 3, 5, 6] 
    N = len(arr)
  
    steps = 10
    printWeightsOnScale(arr, N, steps)
  
# This code is contributed by PranchalK

Producción:

2 3 2 3 5 6 5 3 2 3

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.