求最优组合的递归算法寻求优化方案

Lewe2010 发布于 2018/07/03 14:54
阅读 1K+
收藏 0

开源之夏第三届火热来袭,高校学生参与赢万元奖金!>>>

 下面代码是将一组数字自由组合成一组一组最接近100的数字组合,直到这组数字全部组合完毕的一种解法。由于递归的效率和性能问题,请各路大神给出更优化的方式。

package com.lwc.test;

import org.junit.Test;

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

/**
 * @author li
 * @since 2018/7/2
 */
public class TestShuffle {

    /**
     *
     * @param group
     * @param nums
     * @param max
     * @param start    起始位置
     */
    private void recombinant(List<Integer> group, List<Integer> nums, int max, int start) {

        if(sum(group) == max) {
            nums.removeAll(group);
            return;
        }

        if(start == nums.size()) {
            nums.removeAll(group);
            return;
        }

        // 剩余nums总和小于max
        if(group.size() == nums.size() && sum(group) <= max) {
            nums.removeAll(group);
            return;
        }

        int sum = 0;
        List<Integer> temp = new ArrayList<>();
        List<Integer> temp2 = new ArrayList<>();
        //计算所有的组合,取组合之和最大的那一组()
        for (int i = 0; i < nums.size(); i++) {
            sum += nums.get(i);

            // 和大于最大值 进入下一循环
            if(sum > max) {
                sum = 0;
                continue;
            }
            temp.add(nums.get(i));

            for (int j = start + 1; j < nums.size() && j != i; j++) {
                // 如果temp之和超过max,进入下一循环
                if (sum(temp) + nums.get(j) > max) {
                    continue;
                }
                temp.add(nums.get(j));

                // 保留最靠近临界值的组合
                // 值越小 减去max的绝对值越大 值越大 减去max的绝对值越小
                // 如果temp 小于初始temp和 去除最后加入的num(nums.get(j)是负数)
                if (Math.abs(sum - max) < Math.abs(sum(temp) - max)) {
                    temp.remove(nums.get(j));
                }
                // 否则 将当前的最大和重置为temp和
                else {
                    sum = sum(temp);
                }
            }

            // 当前和重置为0
            sum = 0;

            // 绝对值越小说明组合之和越大
            // temp和 > temp2和 清空temp2并存入当前最大组合
            if (Math.abs(sum(temp) - max) < Math.abs(sum(temp2) - max)) {
                temp2.clear();
                temp2.addAll(temp);
            }
            // 清空temp
            temp.clear();
        }
        // group和 < temp2和, 重新填充result
        if (Math.abs(sum(temp2) - max) < Math.abs(sum(group) - max)) {
            group.clear();
            group.addAll(temp2);
        }

        recombinant(group, nums, max, ++start);
    }

    @Test
    public void shuffle() {
        Integer [] numArray = {10, 33, 21, 52, 18, 99, 74, 43, 51, 91, 6, 54, 39, 39, 17};
        //Integer [] numArray = {10, 33, 21, 52, 18};
        List<Integer> nums = new ArrayList<>(Arrays.asList(numArray));
        while (nums.size() > 0) {
            List<Integer> group = new ArrayList<>();
            this.recombinant(group, nums, 100, 0);
            System.out.println(Arrays.toString(group.toArray()) + " ---- " + sum(group));
        }
    }

    private int sum(List<Integer> list) {
        return list.stream().mapToInt(Integer::intValue).sum();
    }
}
[33, 18, 43, 6] ---- 100
[10, 21, 52, 17] ---- 100
[99] ---- 99
[39, 54] ---- 93
[91] ---- 91
[74] ---- 74
[51] ---- 51

 

加载中
0
0
L
Lewe2010
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
洛锋峰
洛锋峰
该评论暂时无法显示,详情咨询 QQ 群:点此入群
L
Lewe2010
嗯的
0
我的阿登
我的阿登

有更好的解决办法了吗?

L
Lewe2010
没有 没去思考。。
0
L
Lewe2010

激活一下问题

0
L
Lewe2010
该评论暂时无法显示,详情咨询 QQ 群:点此入群
0
L
Lewe2010

没新回复

OSCHINA
登录后可查看更多优质内容
返回顶部
顶部
返回顶部
顶部