Dada uma escala de ponderação e um conjunto de diferentes pesos positivos onde temos uma oferta infinita de cada peso. Nossa tarefa é colocar pesos nos pratos esquerdo e direito da balança, um por um, de modo que os pratos se movam para o lado onde o peso é colocado, ou seja, cada vez que os pratos da balança se movem para lados alternados.
- Recebemos outros 'passos' inteiros de que precisamos para realizar esta operação.
- Outra restrição é que não podemos colocar o mesmo peso consecutivamente, ou seja, se o peso w for tomado, então na próxima etapa, ao colocar o peso no prato oposto, não poderemos pegar w novamente.
Exemplos:
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 pode ser resolvido fazendo DFS entre os estados da escala.
- Percorremos vários estados DFS para a solução onde cada estado DFS corresponderá ao valor real da diferença entre os movimentos esquerdo e direito e a contagem de passos atual.
- Em vez de armazenar os pesos de ambas as panelas, apenas armazenamos o valor do resíduo da diferença e cada vez que o valor do peso escolhido deve ser maior que esta diferença e não deve ser igual ao valor do peso escolhido anteriormente.
- Se for, chamamos o método DFS recursivamente com um novo valor de diferença e mais uma etapa.
Por favor, veja o código abaixo para melhor compreensão
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
Saída:
2 3 2 3 5 6 5 3 2 3
Criar questionário