内容简介：交换数组元素，使得数组的和的差最小
问题描述
设有两个 长度相等的、数值类型的 无序序列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删除数组中指定下标的元素方法
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
