交换数组元素，使得数组的和的差最小

内容简介：交换数组元素，使得数组的和的差最小

问题描述

设有两个 长度相等的、数值类型的 无序序列a，b；

要求：通过交换a，b中的元素，使得[a中所有元素的和] 与 [b中所有元素的和] 的差最小。

求解思路

在逻辑层面将两个序列，看成一个序列。则问题可以转换成：从一个长度为2n的数组中，选出n个元素，使得这n个元素的和接近[两个数组的所有数据元素的和的 一半 ]。

因此可以通过动态规划来求解：

• 状态是
  • offset：某一子阶段可以从[逻辑序列]的该偏移处开始取数据元素
  • alreadySelectSize：在某一子阶段开始前，已经选择的元素的数量，该子阶段应该选择的元素的数量为 n - alreadySelectSize
  • target：某一子阶段所选择的所有的元素的和需要接近的数值
• 状态转移方程是
  dynamicProgramming(offset, alreadySelectSize, target) =
  
  • 当 alreadySelectSize == n 时， 空序列
  • 当 2n - offset + alreadySelectSize == n 时， 逻辑序列[offset...2n]
  • 否则， dynamicProgramming(offset+1, alreadySelectSize, target) 和 [逻辑序列[offset]] + dynamicProgramming(offset+1, alreadySelectSize+1, target-逻辑序列[offset])中所有元素的和更为接近target者

除了使用动态规划之外，还可以使用回溯算法求出所有可能的解，然后再从中选择最优的解。

代码实现

package cn.timd.DynamicProgramming;

import java.math.BigDecimal;  
import java.util.ArrayList;  
import java.util.List;  
import java.util.Stack;

public class MinDifference {  
    private List<BigDecimal> firstList;
    private List<BigDecimal> secondList;
    private BigDecimal target;
    private int size;
    private int shouldSelectSize;

    public MinDifference(List<BigDecimal> firstList, List<BigDecimal> secondList) {
        if (firstList == null || secondList == null)
            throw new RuntimeException("firstList == null or secondList == null");
        if (firstList.size() == 0 || firstList.size() != secondList.size())
            throw new RuntimeException("invalid firstList or secondList");

        this.firstList = firstList;
        this.secondList = secondList;
        target = getSum(firstList, secondList).divide(new BigDecimal(2)); // average
        size = firstList.size() + secondList.size();
        shouldSelectSize = size / 2;
    }

    private BigDecimal getSum(List<BigDecimal>... lists) {
        BigDecimal sum = new BigDecimal(0);
        for (List<BigDecimal> list: lists)
            for (BigDecimal element: list)
                sum = sum.add(element);
        return sum;
    }

    private BigDecimal getTarget() {
        return target;
    }

    public int getSize() {
        return size;
    }

    public BigDecimal get(int n) {
        if (n < 0 || n >= getSize())
            throw new RuntimeException("invalid index");
        if (n < firstList.size())
            return firstList.get(n);
        return secondList.get(n - firstList.size());
    }

    public int getShouldSelectSize() {
        return shouldSelectSize;
    }

    private List<BigDecimal> dynamicProgramming(int offset, int alreadySelectSize, BigDecimal target) {
        List<BigDecimal> decision = new ArrayList<BigDecimal>();
        if (getSize() - offset + alreadySelectSize == getShouldSelectSize()) {
            for (int n = offset; n < getSize(); ++n)
                decision.add(get(n));
            return decision;
        }

        if (alreadySelectSize == getShouldSelectSize())
            return decision;

        List<BigDecimal> notChooseOffset = dynamicProgramming(offset+1, alreadySelectSize, target);
        List<BigDecimal> chooseOffset = new ArrayList<BigDecimal>();
        chooseOffset.add(get(offset));
        chooseOffset.addAll(dynamicProgramming(offset+1, alreadySelectSize+1, target.subtract(get(offset))));

        BigDecimal notChooseOffsetSum = getSum(notChooseOffset);
        BigDecimal chooseOffsetSum = getSum(chooseOffset);

        if (notChooseOffsetSum.subtract(target).abs().compareTo
                (chooseOffsetSum.subtract(target).abs()) < 0)
            return notChooseOffset;
        return chooseOffset;
    }

    public List<BigDecimal> dynamicProgramming() {
        return dynamicProgramming(0, 0, getTarget());
    }

    private static class Node {
        BigDecimal element;
        List<Node> nextNodes;
        int offset = 0;

        Node(BigDecimal element) {
            this.element = element;
        }

        Node getNextNode() {
            if (nextNodes == null || offset >= nextNodes.size())
                return null;
            return nextNodes.get(offset++);
        }

        void clear() {
            offset = 0;
        }
    }

    private Node createNodes() {
        Node root = new Node(null);

        List<Node> nodes = new ArrayList<Node>();
        for (int i = 0; i < getSize(); ++i)
            nodes.add(new Node(get(i)));
        root.nextNodes = nodes;
        for (int i = 0; i < getSize() - 1; i++)
            nodes.get(i).nextNodes = nodes.subList(i+1, nodes.size());
        return root;
    }

    public List<BigDecimal> backTrace() {
        BigDecimal totalSum = getSum(firstList, secondList);
        List<BigDecimal> result = null;
        BigDecimal currentAbs = null;

        Node root = createNodes();
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        Node extensionNode, nextNode;

        while (!stack.empty()) {
            extensionNode = stack.peek();
            nextNode = extensionNode.getNextNode();
            if (nextNode == null) {
                extensionNode = stack.pop();
                if (stack.empty())
                    break;
                extensionNode.clear();
            } else {
                if (stack.size() == getShouldSelectSize()) {
                    List<BigDecimal> list = new ArrayList<BigDecimal>();
                    for (Node node: stack)
                        if (node != root)
                            list.add(node.element);
                    list.add(nextNode.element);

                    BigDecimal abs = getSum(list).multiply(new BigDecimal(2)).subtract(totalSum).abs();
                    if (currentAbs == null || abs.compareTo(currentAbs) < 0) {
                        result = list;
                        currentAbs = abs;
                    }
                } else
                    stack.push(nextNode);
            }
        }
        return result;
    }

    public static void test(String[] args) {
        int[] firstArray = new int[]{12, 19, 8, 3, 16, 13, 4, 7, 1, 2};
        int[] secondArray = new int[]{10, 6, 18, 5, 11, 17, 9, 14, 20, 15};
        List<BigDecimal> firstList = new ArrayList<BigDecimal>();
        List<BigDecimal> secondList = new ArrayList<BigDecimal>();

        for (int element: firstArray)
            firstList.add(new BigDecimal(element));
        for (int element: secondArray)
            secondList.add(new BigDecimal(element));

        MinDifference minDifference = new MinDifference(firstList, secondList);
        for (BigDecimal element: minDifference.backTrace())
            System.out.print(element.toString() + " ");
        System.out.println();

        for (BigDecimal element: minDifference.dynamicProgramming())
            System.out.print(element.toString() + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        test(args);
    }
}

执行结果：

文档

• 动态规划
• 最优化原理
• 回溯算法

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• LeetCode-数组-删除元素
• 求非负元素数组所有元素能组合的最大字符串
• 前端通关日记之优雅添加数组元素
• [译] 对元素持有弱引用的 Swift 数组
• [译] 对元素持有弱引用的 Swift 数组
• PHP删除数组中指定下标的元素方法

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。