在给定约束条件下交替移动权重比例

给定一个权重标度和一系列不同的正权重，其中每个权重的供应是无限的。我们的任务是将砝码一个接一个地放在天平的左右盘上，使天平移动到放置砝码的那一侧，即每次天平盘移动到另一侧。

• 我们得到了另一个整数“步数”，即执行此操作所需的时间。
• 另一个限制是，我们不能连续放置相同的重量，也就是说，如果取了重量w，那么在下一步中，当把重量放在另一个盘子上时，我们不能再取w。

  例如：

  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.
  

  推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

  这个问题可以通过做某事来解决 DFS 在各州之间。

  1. 我们在各种DFS状态之间进行遍历，以获得解决方案，其中每个DFS状态将对应于左右平移和当前步长计数之间的实际差值。
  2. 我们不存储两个盘子的重量，只存储差值剩余值，每次选择的重量值应大于此差值，且不应等于之前选择的重量值。
  3. 如果是，那么我们使用新的差值和一个步骤递归调用DFS方法。

  请参阅下面的代码以更好地理解，

  C++

  // 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" ; } //    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

  // 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

  # 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

  输出：

  2 3 2 3 5 6 5 3 2 3
  

  本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

  如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。