java - 我们如何将一个数组分成两个重量差异最小的新数组？

Question

我正在做以下编程练习：Stone pile。声明是：

你得到一堆不同重量的石头。

你的任务是将这堆石堆分成两部分，这样两堆之间的重量差异就会很小。你不能把一块石头打成更小的石头。

例如，如果我们有石头：

[1、2、3、4]

我们可以将它们分为：

[2, 3], [1, 4]

所以差值为0

如果给你的是空石堆，你仍然可以将它分成两堆没有石头的堆。

该堆将包含最多 22 块石头。

按照我想到的例子：

Sort stones in ascending order
for each stone
 if length is even
  if movement is even
   add min and max to right list
   remove them
  if movement is odd
   add min and max to left list
   remove them

 if length is odd
  if movement is even
   add max to left
   remove it
  if movement is odd
   add min to right
   remove it
   if there are more items
   add next min
   remove it

所以在代码中是：

import java.util.*;
import java.util.stream.*;

public class Pile {
    public static int minDiff(int[] stones) {
      System.out.println("stones: "+Arrays.toString(stones));
      Arrays.sort(stones);
      System.out.println("stones: "+Arrays.toString(stones));

      List<Integer> allStones = Arrays.stream(stones).boxed().collect(Collectors.toList());
      System.out.println("allStones: "+Arrays.toString(allStones.toArray()));
      ArrayList<Integer> left = new ArrayList<>();
      ArrayList<Integer> right = new ArrayList<>();

      for(int i = 0; allStones.size()>0; i++){
        if(stones.length%2==0){
          if(i%2==0){
            right.add(allStones.get(0));
            right.add(allStones.get(allStones.size()-1));
            allStones.remove(0);
            allStones.remove(allStones.size()-1);
          }else{
            left.add(allStones.get(0));
            left.add(allStones.get(allStones.size()-1));
            allStones.remove(0);
            allStones.remove(allStones.size()-1);
          }
        }else{
          if(i%2==0){
            left.add(allStones.get(allStones.size()-1));
            allStones.remove(allStones.size()-1);
          }else{
            right.add(allStones.get(0));
            allStones.remove(0);
            if(allStones.size()>0){
              right.add(allStones.get(0));
              allStones.remove(0);
            }
          }
        }
      }
      System.out.println("left: "+Arrays.toString(left.toArray()));
      System.out.println("right: "+Arrays.toString(right.toArray()));
      return left.stream().mapToInt(Integer::intValue).sum()-right.stream().mapToInt(Integer::intValue).sum();
    }
}

目前，当我们使用差异为零的输入对其进行测试时，它才起作用。但是，如果我们使用其他输入对其进行测试，它将失败。

鉴于以下测试，第一个套件将通过，其他套件将失败：

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class PersonTest {

    @Test
    public void testDifferenceShouldBeZero(){
        assertEquals(0, Pile.minDiff(new int[]{1, 2, 3}));
        assertEquals(0, Pile.minDiff(new int[]{1, 2, 3, 4}));
        assertEquals(0, Pile.minDiff(new int[]{5,5,4,3,3}));
    }

    @Test
    public void testDifferenceShouldBeOne(){
        assertEquals(1, Pile.minDiff(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}));
    }

    @Test
    public void testDifferenceShouldBeTwo(){
        assertEquals(2, Pile.minDiff(new int[]{89409, 34351, 3065, 10128, 27694, 27585, 87350, 33875, 2658, 41606, 57512, 73368, 83345, 37048, 31827, 94644, 15972, 74813, 31441, 70395}));
    }

}

例如，当石头是：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]

跟踪是：

stones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
stones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
allStones: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22]
left: [2, 21, 4, 19, 6, 17, 8, 15, 10, 13]
right: [1, 22, 3, 20, 5, 18, 7, 16, 9, 14, 11, 12]

结果：

预期：<1> 但结果：<-23>

对于一般情况，我们如何将石堆分成两块差异最小的块？

我们已阅读：

• 复制数组
• 如何在 Java 中将 int[] 转换为 List<Integer>？
• 如何获取 ArrayList 的最后一个值
• 是否有可能在没有循环的情况下对 ArrayList 进行总和

标签： javaarraysalgorithmsplitint

Answer 1

我会使用位组合将石头分成两组并总结所有可能的组合，比较它们以选择差异最小的一组：

import java.util.Arrays;
import java.util.LinkedList;

public class Pile {
    /**
     * return solution as int, if bit is set use the "bitNumber" as index for stone
     * for one side, otherwise for the other
     **/
    private static int divide(int[] stones) {
        int solution = -1;
        long minDifference = Long.MAX_VALUE;
        for (int n = 0; n < (1 << (stones.length + 1)); n++) {
            long sumLeft = 0;
            long sumRight = 0;
            for (int bit = 0; bit < stones.length; bit++) {
                boolean isSet = (n & (1 << bit)) > 0;
                if (isSet) {
                    sumLeft += stones[bit];
                } else {
                    sumRight += stones[bit];
                }

            }
            long diff = Math.abs(sumLeft - sumRight);
            if (diff < minDifference) {
                solution = n;
                minDifference = diff;
            }

        }
        return solution;
    }

    public static long minDiff(int[] stones) {
        int solution = divide(stones);
        long sumLeft = 0;
        long sumRight = 0;

        LinkedList<Integer> left = new LinkedList<>();
        LinkedList<Integer> right = new LinkedList<>();
        for (int bit = 0; bit < stones.length; bit++) {
            boolean isSet = (solution & (1 << bit)) > 0;
            if (isSet) {
                sumLeft += stones[bit];
                left.add(stones[bit]);
            } else {
                sumRight += stones[bit];
                right.add(stones[bit]);
            }
        }
        System.out.println("left: " + Arrays.toString(left.toArray()));
        System.out.println("right: " + Arrays.toString(right.toArray()));
        return Math.abs(sumRight - sumLeft);
    }

}