Gitt en vektingsskala og en rekke forskjellige positive vekter der vi har en uendelig tilførsel av hver vekt. Vår oppgave er å legge vekter på venstre og høyre skala en etter en på en slik måte at pannene beveger seg til den siden hvor vekten legges, dvs. hver gang skalaen beveger seg til alternerende sider.
- Vi får enda et heltall "trinn" ganger som vi trenger for å utføre denne operasjonen.
- En annen begrensning er at vi ikke kan legge samme vekt fortløpende, det vil si at hvis vekten w tas, kan vi ikke ta w igjen i neste trinn mens vi legger vekten på motsatt panne.
Eksempler:
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.
Dette problemet kan løses ved å gjøre DFS blant skalatilstander.
- Vi krysser mellom forskjellige DFS-tilstander for løsningen der hver DFS-tilstand vil tilsvare faktisk forskjellsverdi mellom venstre og høyre panorering og gjeldende trinnteller.
- I stedet for å lagre vektene til begge pannene lagrer vi bare forskjellsrestverdien, og hver gang valgt vektverdi skal være større enn denne forskjellen og bør ikke være lik tidligere valgt vektverdi.
- Hvis det er det, kaller vi DFS-metoden rekursivt med ny differanseverdi og ett trinn til.
Se koden nedenfor for bedre forståelse
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
Produksjon:
2 3 2 3 5 6 5 3 2 3
Lag quiz