java将元素划分为一个组
我给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;
}
但是这种方法对于非常大的数据量是失败的,有人能帮我在这方面如何使用动态规划,这样我就不会重复调用了
# 1 楼答案
获取一个标志数组,该数组为每个元素标记它们是否包含在结果中。从不包含任何内容开始,递归地尝试每个元素,如果包含它是否能提供正确的结果