Dada una escala de ponderación y una serie de pesos positivos diferentes donde tenemos un suministro infinito de cada peso. Nuestra tarea es colocar pesas en los platillos izquierdo y derecho de la balanza, uno por uno, de tal manera que los platillos se muevan hacia el lado donde se coloca el peso, es decir, cada vez que los platillos de la balanza se mueven hacia lados alternos.
- Se nos dan otros tiempos de "pasos" enteros 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, en el siguiente paso mientras colocamos 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 los estados de escala.
- Atravesamos varios estados DFS para encontrar la solución donde cada estado DFS corresponderá al valor de diferencia real entre los paneos izquierdo y derecho y el recuento de pasos actual.
- En lugar de almacenar los pesos de ambos platos, simplemente almacenamos el valor del residuo 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 previamente elegido.
- Si es así, llamamos al método DFS de forma recursiva con un nuevo valor de diferencia y un paso más.
Consulte el código a continuación para una mejor comprensión.
C++// C++ program to print weights for alternating // the weighting scale #include
// 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
// C# program to print weights for alternating // the weighting scale using System; namespace GFG { class Program { // DFS method to traverse among states of weighting scales static 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 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++) Console.Write(wt[i] + ' '); Console.WriteLine(); } else Console.WriteLine('Not Possible'); } static void Main(string[] args) { int[] arr = { 2 3 5 6 }; int N = arr.Length; int steps = 10; printWeightOnScale(arr N steps); } } }
function 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 (let i = 0; i < N; i++) { /* Try this weight only if it is greater than current residue and 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; } function printWeightsOnScale(arr N steps) { const wt = new Array(steps); // call dfs with current residue as 0 and current // steps as 0 if (dfs(0 1 wt arr N steps)) { for (let i = 1; i <= steps; i++) { process.stdout.write(`${wt[i]} `); } console.log(); } else { console.log('Not possible'); } } const arr = [2 3 5 6]; const N = arr.length; const steps = 10; printWeightsOnScale(arr N steps); // This code is contributed by divyansh2212
Producción:
2 3 2 3 5 6 5 3 2 3
Crear cuestionario