重みの配列によるスケールの調整

Question

次のプロンプトが表示されています。 スケールの片側に重みがあるとします。他の重みの配列がある場合は、スケールが均衡するかどうかを確認してください。どちらの側でもウェイトを使用することができ、すべてのウェイトを使用する必要はありません。

私はjavascriptを使用してソリューションを実装しようとしていますが、マッチするまで重みを累積することで問題の1つを解決できました。最終的にこれはスケールの左側に追加する場合にのみ機能しますが、右側にも重みを追加できることを考慮すると最適ではありません。以下はこれまでの私の実装です。

const balance = (arrayOfWeights) => { 
 
    //Sort the array and pop off the max number to be stored on the right side of the scale 
 
    let right = arrayOfWeights.sort().pop(); 
 
    let balanced; 
 
    let weight; 
 

 
    const subroutine = (lSide, rSide, weightList) => { 
 
    //Determine if there is a direct match 
 
    if(lSide === rSide) { 
 
     balanced = true; 
 
     return balanced; 
 
    } 
 
    //Return false if a match hasn't been found 
 
    if(weightList.length === 0) { 
 
     balanced = false; 
 
     return balanced 
 
    } 
 
    //Shift the first element of the array to be added to left side 
 
    weight = weightList.shift(); 
 
    subroutine(lSide + weight , rSide, weightList); 
 
    } 
 
    subroutine(0, right, arrayOfWeights); 
 
    return balanced; 
 
}; 
 

 
//Array of weights to be passed to balance function 
 
let weights = [3,6,2,5,1];

Answer 1

私が正しくあなたの問題を理解していた場合は、単にすべてのコンボを通過するいくつかの基本的な再帰を使用することができます。

1. include the weight on the left 
2. include the weight on the right 
3. dont include the weight 

一般的な考え方は次のようになります：

0は kに含まれていない重量を表し、 1が含ま kで体重を表し

f(A[],k,n){ 
    if(weights on both sides are euqal) return 
    if(k==n) return 
    A[k]=0 //not included 
    f(A,k+1,n) 
    A[k]=1 // included on the left 
    f(A,k+1,n) 
    A[k]=2 // included on the right 
    f(A,k+1,n) 
} 

あなたは3つのオプションを持っている状況があるとし2は、右側に含まれるkの重量を表します。これは私がJavaで行ったことです（多くのjavascriptを知らない）：

static void print(int A[],int B[]) { 
     for (int i = 0; i < A.length; i++) { 
      if(A[i]==1) System.out.println(B[i]+" is on the left"); 
      else if(A[i]==2) System.out.println(B[i]+" is on the right"); 
     } 
     System.out.println(); 
    } 
    static boolean sum(int A[],int B[],int[] w){ 
     int left=0; 
     int right=0; 
     if(w[1]==1) left+= w[0]; 
     else if (w[1]==2) right+= w[0]; 

     for(int i=0;i<A.length;i++){ 
      if(A[i]==1) left+= B[i]; 
      if(A[i]==2) right+= B[i]; 
     } 
     if(right==left) return true; 

     return false; 
    } 


    static void g(int A[],int B[],int k,int n,int[] w){ 

     if(sum(B,A,w)){//works 
      print(B,A); 
      return; 
     } 
     if(k==n) return;//doesnt work 

     B[k]=0;//not included 
     g(A,B,k+1,n,w); 
     B[k]=1;//included on the left 
     g(A,B,k+1,n,w); 
     B[k]=2;//included on the right 
     g(A,B,k+1,n,w); 

    } 
    public static void main(String[] args) { 
     int A[] = {4,5,6,7};//array of weights 

     // put 0 if ith element not included 
     // put 1 if ith element is on the left 
     // put 2 if ith element is on the right 
     int B[] = new int[A.length]; 

     // weight you start with: 
     // w[0] is weight amount w[1] 
     // is whether its on the left right or neither (1,2,0) 
     int[] w = {6,1}; 
     g(A,B,0,A.length,w); 
    }