將一個元素劃分成一個組

Question

我給出了N個元素及其權重，而且我只需從中選取其中的M個元素，使得它們的權重除以k。

For Ex: 
N=5 
Weight:1 2 3 4 5 
M =3 
K=5 
so we will pick up : 1 4 5 as total 10 is divide by 5. So ans =10 

我的方法：使用遞歸函數

public static int ans(int[] a,int m,int k,int total){ 
     int sum=0; 
     if(a.length<m) 
     return Integer.MAX_VALUE; 
     if(m==0){ 
      //System.out.println("ok"); 
      if(total%k==0) 
       return total; 
      else 
       return Integer.MAX_VALUE; 
     } 
     int[] temp = new int[a.length-1]; 
     for(int j=0;j<temp.length;j++) 
      temp[j]=a[j]; 

     sum = Math.min(ans(temp,m,k,total), ans(temp,m-1,k,total+a[a.length-1])); 




     return sum; 
    } 

但這種方法失敗的數據量非常大的，有人可以幫助我如何使用動態規劃在此，讓我不t重複呼叫。

Answer 1

獲取一個標記數組，標記每個元素是否包含在結果中。從包含任何東西開始，如果包含它可以提供正確的結果，則遞歸地嘗試每個元素。