在一个无序的数组中,实现一个或者多个元素相加小于给定的目标数,所有的可能。 20C

七个用户确定的数,a,b,c,d,e,f,g,任选其中的m(1<=m<=7)个数,不重复选,求和sum,使sum<n,n是用户确定的一个数。
求所有可能的组合。

用户输入a,b,c,d,e,f,g和n,
程序输出多有可能的组合

3个回答

可以把确定的数字组成数组,获取所有的数组组合,再挑选和符合条件的组合,这里介绍一下按位对应法来获取所有数组组合

            final Integer[] arr = new Integer[] { 1, 2, 3, 5, 6, 7, 8 };
    final int end = 1 << arr.length;
    for (int start = 1; start < end; start++) {
        int sum = 0;
        final List<Integer> ls = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (((1 << i) & start) != 0) {// 该位有元素输出
                sum += arr[i];
                ls.add(arr[i]);
            }
        }
        if (sum < 7) {
            System.out.println(Arrays.toString(ls.toArray()));
        }
    }
qq_36803548
skptch 请问这个可以改写成 c或者是c++嘛
2 年多之前 回复

可以换一个角度考虑,给定的数如果是M,那么针对数组中一个数字N,我们只需要查找一下数

组中是否含有M-N就可以了,这样就转换为数组查找问题了,然后可以利用空间换时间来搞

定,搞一个hash表,然后把每一个都映射到hash表中去,然后查找的时候就需要O(1)就可以
了,只不过空间复杂度达到O(N)

qq_36803548
skptch 可以具体点 嘛。。 谢谢了
2 年多之前 回复

import java.util.Scanner;

/**

  • 在一个无序的数组中,实现一个或者多个元素相加小于给定的目标数,所有的可能。 20C 数据结构 七个用户确定的数,a,b,c,d,e,f,g,任选其中的m(1<=m<=7)个数,不重复选,求和sum,使sum<n,n是用户确定的一个数。 求所有可能的组合。

用户输入a,b,c,d,e,f,g和n,
程序输出多有可能的组合

  • @author * */ public class Test06 { public static void main(String[] args) { ImplementClass im = new ImplementClass(); im.implementMethod(); } } class ImplementClass{ public void implementMethod(){ Scanner sc = new Scanner(System.in); int[] arr = new int[7]; System.out.print("请输入7个确定的数(空格隔开):"); for(int i=0;i<arr.length;i++){ arr[i] = sc.nextInt(); } System.out.print("请输入m(1<=m<=7):"); int m = sc.nextInt(); System.out.print("请输入n:"); int n = sc.nextInt();//最后比较大小的数 int count = 0; if(m == 1){ for(int a:arr){ if(implementMethod2(a)<n){ count++; huanHang(count); System.out.print(a+","); } } }else if(m == 2){ for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ int temp = implementMethod2(arr[i],arr[j]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+","); } } } }else if(m == 3){ for(int i=0;i<arr.length-2;i++){ for(int j=i+1;j<arr.length-1;j++){ for(int k=i+2;k<arr.length;k++){ int temp = implementMethod2(arr[i],arr[j],arr[k]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+","); } } } } }else if(m ==4){ for(int i=0;i<arr.length-3;i++){ for(int j=i+1;j<arr.length-2;j++){ for(int k=i+2;k<arr.length-1;k++){ for(int l=i+3;l<arr.length;l++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+","); } } } } } }else if(m ==5){ for(int i=0;i<arr.length-4;i++){ for(int j=i+1;j<arr.length-3;j++){ for(int k=i+2;k<arr.length-2;k++){ for(int l=i+3;l<arr.length-1;l++){ for(int m2=i+4;m2<arr.length;m2++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+","); } } } } } } }else if(m ==6){ for(int i=0;i<arr.length-5;i++){ for(int j=i+1;j<arr.length-4;j++){ for(int k=i+2;k<arr.length-3;k++){ for(int l=i+3;l<arr.length-2;l++){ for(int m2=i+4;m2<arr.length-1;m2++){ for(int n2=i+5;n2<arr.length;n2++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2],arr[n2]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+" "+arr[n2]+","); } } } } } } } }else if(m ==7){ for(int i=0;i<arr.length-6;i++){ for(int j=i+1;j<arr.length-5;j++){ for(int k=i+2;k<arr.length-4;k++){ for(int l=i+3;l<arr.length-3;l++){ for(int m2=i+4;m2<arr.length-2;m2++){ for(int n2=i+5;n2<arr.length-1;n2++){ for(int o=i+6;o<arr.length;o++){ int temp = implementMethod2(arr[i],arr[j],arr[k],arr[l],arr[m2],arr[n2],arr[o]); if(temp<n){ count++; huanHang(count); System.out.print(arr[i]+" "+arr[j]+" "+arr[k]+" "+arr[l]+" "+arr[m2]+" "+arr[n2]+" "+arr[o]+","); } } } } } } } } } System.out.println("\nm="+m+",n="+n+"的时候,可能的组合数"+count); } //输出6个组合换行 public void huanHang(int count){ if(count%7 == 0) System.out.println(); } public int implementMethod2(int...m){ int sum = 0; for(int temp:m){ sum += temp; } return sum; } }
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问