求助一个算法,JAVA

Freonever 发布于 12/05 16:02
阅读 558
收藏 0

如题,需求是从最多10个整数的集合中,分成两组(不需平均分组,可以一组1个、另一组9个),要求只要两组的总和差值最小,还有就是集合里的数量可奇可偶。

加载中
0
Freonever
Freonever

目前自己想到的办法是。

1、从小到大排序。

2、最小的给A,最大的给B。

3、循环剩余的数组

4、将剩余的数字求和,为X

5、A中的值加上X与B比较。如果A+X>B,则将数组中最小的值放入A数组,并从数组中剔除该值,否则不做操作,处理后,数组为Y

6、B中的值加上Y与A比较,如果B+X>A,则将数组中最小的值放入B数组,并从数组中剔除该值,否则不做操作。

7、重复3-6,至数组为空。

有无其他解?

Freonever
Freonever
回复 @隆回水哥 : 发现了,我自己写的有问题,所以问题还在考虑,脑阔想的疼
隆回水哥
隆回水哥
最小的和最大的不一定在不同的组,有可能在同一组。比如{1, 3, 3, 3, 3, 10}。1和10在一组,四个3在一组,差值是1
0
foy
foy

问题转化为,求数组中的m个数的和尽量接近整个数组和的一半。

转化为一个01背包问题。

Freonever
Freonever
01背包遗忘干净
0
雪花飘飘一人醉
雪花飘飘一人醉

n个整数先算出几种分法,如5个数有两种分法,一组1个数一组4个数和一组3个树和一组4个数,

随机生成5个数字的数组,循环各种分法下两组数据的和的差值并记录下差值和各个分组数字情况,

每种分法下的情况有n!/(m1!m2!),m1+m2=n,如m1=1,m2=4,共有五种,

按顺序五种每个取一个值,组成一组,其余为另一组,其他情况类似按顺序取多个值即可,计算差值并记录,这样循环所有分组情况,进行最后差值比较选出最小的那一组。

 

这是遍历所有分组情况进行汇总比较的思路!

0
精神兵
public class ArithmeticTest {
    private static List<String> ll = new ArrayList<>();
    //map中的key为ll中的索引,value为总和与平均值的绝对值
    private static Map<Integer, Integer> sums = new TreeMap<>();

    public static void main(String[] args) {
        List<Integer> list = Lists.newArrayList(1, 2, 4, 7, 9, 11, 99);
        Integer avg = Math.toIntExact(list.stream().mapToInt(Integer::intValue).summaryStatistics().getSum() / 2);
        getSubset(list);
        for (int m = 0; m < ll.size(); m++) {
            Integer sum = 0;
            String[] split = ll.get(m).split(",");
            for (String aSplit : split) {
                sum += Integer.valueOf(aSplit);
            }
            Integer abs = Math.abs(avg - sum);
            sums.put(m, abs);
        }
        //记录排序后的索引
        List<Integer> indexs = new ArrayList<>();
        sums.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEachOrdered(x -> indexs.add(x.getKey()));
        System.out.println(ll.get(indexs.get(0)));
    }

    private static void getSubset(List<Integer> set)
    {
        int length = set.size();
        int i;

        for( i=1;i<(1<<length);i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<length;j++){
                if((i&(1<<j))!=0){
                    sb.append(set.get(j)).append(",");
                }
            }
            ll.add(sb.toString());
        }
    }

}
Freonever
Freonever
回复 @精神兵 : 好的,先谢谢了
精神兵
回复 @Freonever : 将集合中所有数相加除以2的结果与集合的子集相加的结果比较,查找最接近的,JDK8环境下代码可以运行,你可以试试
Freonever
Freonever
表示没看懂。。。
0
ZhouJunhua
ZhouJunhua
// 从大到小排好序的数组
int[] arr = {99,11,9,7,4,2,1};
List<Integer> groupA = new ArrayList<>();
List<Integer> groupB = new ArrayList<>();
int sumA = 0;
int sumB = 0;
for (int i = 0; i < arr.length; i++) {
	if (sumA <= sumB) {
		groupA.add(arr[i]);
		sumA += arr[i];
	} else {
		groupB.add(arr[i]);
		sumB += arr[i];
	}
}
System.out.println("A:" + groupA + ", B: " + groupB + ", 差值:" + Math.abs(sumA - sumB));
// A:[99], B: [11, 9, 7, 4, 2, 1], 差值:65

这样可以么

ZhouJunhua
ZhouJunhua
回复 @捉鬼大帝 : 从大到小排序后是:{10,3,3,3,3,1},执行结果:A: [10, 1], B: [3, 3, 3, 3], 差值:1
捉鬼大帝
捉鬼大帝
{1,3,3,3,3,10}
小_橙_子
喔,不好意思。没注意看前提。能否讲解一下这个代码的算法思路呢?回复 @隆回水哥 :
Freonever
Freonever
回复 @小_橙_子 : 不对撒
隆回水哥
隆回水哥
回复 @Freonever : 尝试了,没毛病。重要的是先要从大到小排序,这样大数就尽可能均匀的分开到两组。
下一页
0
Mr_祝靖俊
Mr_祝靖俊

C(n/10)的问题,n=1,2,3,4,5

0
Freonever
Freonever
自己又想到一解。 1、列出所有组合可能性 2、找出每组差值最小的 3、如果存在相同的。。。。。。。。就全部列出来
0
Freonever
Freonever

自己又想到一解。

1、列出所有组合可能性

2、找出每组差值最小的

3、如果存在相同的。。。。。。。。就全部列出来

0
捉鬼大帝
捉鬼大帝

import java.util.ArrayList;
import java.util.Arrays;

public class T {
    public static void main(String[] args) {
        int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
        }
        table(sum / 2, array);
    }

    static void table(int avg, int[] array) {
        int n = array.length;
        int[][] f = new int[n + 1][avg + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= avg; j++) {
                if (j >= array[i - 1]) {
                    f[i][j] = Math.max(f[i - 1][j - array[i - 1]] + array[i - 1], f[i - 1][j]);
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        int x = avg;
        ArrayList<Integer> array2 = new ArrayList();
        for (int i = 0; i < array.length; i++) {
            array2.add(array[i]);
        }
        System.out.print("第一组:");
        for (int i = n; i > 0; i--) {
            if (f[i][x] > f[i - 1][x]) {
                int v = array[i - 1];
                System.out.print(v + "\t");
                x -= v;
                if (array2.indexOf(v) > -1) {
                    array2.remove(array2.indexOf(v));
                }
            }
        }
        System.out.print("\n第二组:");
        for (int i = 0; i < array2.size(); i++) {
            System.out.print(array2.get(i) + "\t");
        }
    }
}

 

捉鬼大帝
捉鬼大帝
回复 @Freonever : 看题目,只要两组的总和差值最小,也就是说,两组的和都无限趋于(原数组的和/2)呗。 那么这个问题其实就是典型的背包问题的变形: 设有原数组array 一个背包有sum(array)/2大小,问如何才能尽可能大的填满背包。 然后填满背包后,背包里的是一组,剩余的array是另外一组。 典型的背包问题。
Freonever
Freonever
然后还是没看懂逻辑,求解释下。
Freonever
Freonever
目前看,就这个方法的结果是对的
返回顶部
顶部