三个数字相加小于某个值的所有可能组合这个算法怎么求,例如100,90,80,相加要少于500,可以有80+80,或者100,或者100+90+80

开源中国首席罗纳尔多 发布于 2017/07/31 17:02
阅读 504
收藏 1

三个数字相加小于某个值的所有可能组合这个算法怎么求,例如100,90,80,相加要少于500,可以有80+80,或者100,或者100+90+80

 

自己手动列可以有 80,80+80,80+80+80,80+90+90等等。。。而且是上限值是500的时候,如果改成1000,10000就有更多了,所以想问一下算法怎么写好。。。

加载中
1
烟雨三月
烟雨三月
public class Q3376901_2262676 {

  public static void main(String[] args) {
    int[] num = new int[] { 100, 90, 80 };
    int t = 500;
    int[] count = new int[num.length];
    s(num, count, 0, t);
  }

  public static void s(int[] num, int[] count, int i, int t) {
    if (t <= 0 || i >= num.length) {
      print(num, count);
      return;
    }

    if (num[i] < t) {
      count[i]++;
      s(num, count, i, t - num[i]);
      count[i]--;
    }
    s(num, count, i + 1, t);
  }

  private static void print(int[] num, int[] count) {
    boolean f = true;
    for (int i = 0; i < num.length; i++) {
      for (int j = 0; j < count[i]; j++) {
        if (!f) {
          System.out.print("+");
        } else {
          f = false;
        }
        System.out.print(num[i]);
      }
    }
    if (!f) {
      System.out.println();
    }
  }
}

 

开源中国首席罗纳尔多
开源中国首席罗纳尔多
你的算法好复杂,看不懂,请问是什么原理,已给最佳。
返回顶部
顶部