将一个元素划分成一个组

我给出了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重复呼叫。

来源

2014-10-16 user4116864

我的要求并不清楚。前三个元素（权重为1，1和3）呢？他们也加起来重量5.通常，有不止一种可能的解决方案。另外，可能没有解决办法。你的算法应该提供什么？我也看到，你只返回一个int。这怎么可能是一个解决方案？ – Seelenvirtuose 2014-10-16 11:07:40

@Seelenvirtuose [链接]（http://www.codechef.com/problems/BUYING） – user4116864 2014-10-16 11:12:00

如何将输入值按其余模'K'分组？ – CiaPan 2014-10-16 11:55:56

获取一个标记数组，标记每个元素是否包含在结果中。从包含任何东西开始，如果包含它可以提供正确的结果，则递归地尝试每个元素。

来源

2014-10-16 12:02:27

将一个元素划分成一个组

回答

相关问题