Java 中的拔河比赛

10 Sept 2024 | 5 分钟阅读

在拔河问题中，我们需要将给定的 n 个整数集分成两个大小相等或几乎相等的子集。给定的集合必须这样划分，使得第一个子集中的整数之和与第二个子集中的整数之和的差值最小。如果 n 是偶数，则每个子集的大小必须等于 n / 2。如果 n 是奇数，则一个子集的大小必须是 n / 2，另一个子集的大小是 (n + 1) / 2。让我们通过一些例子来理解。

注意：上面提到的最小差值是指两个子集和之差的绝对值。换句话说，忽略差值的符号，只考虑其大小。

示例 1

S = {-3, 5, 4, 3, 1, 100, 54, 89, 20, 23}，其中 S 是包含 10 个元素的集合。

显然，10 是一个偶数。因此，我们将从给定集合创建的两个子集的大小必须各为 5（10 / 2 = 5）。这两个子集是

S1 = {4, 1, 100, 20, 23} 和 S2 = {-3, 5, 3, 54, 89}

子集 S1 的和是 4 + 1 + 100 + 20 + 23 = 148

子集 S2 的和是 -3 + 5 + 3 + 54 + 89 = 148

因此，我们看到子集 S1 的和等于子集 S2 的和。所以，两个子集的差值是 148 - 148 = 0，这是最小的。

示例 2

S = {-34, 23, 98, 45, 12, 4, 4, -99, -1, 189, 0}，其中 S 是包含 11 个元素的集合。

显然，11 是一个奇数。因此，我们将从给定集合创建的两个子集的大小必须分别是 5（10 / 2 = 5）和 6（10 / 5 + 1 = 6）。这两个子集是

S1 = {45, -34, 12, 98, -1} 和 S2 = {23, 4, 4, -99, 189, 0}

子集 S1 的和是 45 -34 + 12 + 98 -1 = 120

子集 S2 的和是 23 + 4 + 4 -99 + 189 + 0 = 121

因此，我们看到子集 S1 的和与子集 S2 的和不相等。两个子集的差值是 121 - 120 = 1。如果我们创建其他大小相同的子集对，就无法获得小于 1 的差值。因此，1 是给定集合可能获得的最小差值。

方法

以下解决方案会遍历所有可能的半尺寸子集。如果创建了第一个半尺寸的子集，那么剩余的元素就会构成另一个子集。我们初始化当前集为空集，然后向其中填充元素。对于每个元素，我们有两种可能性：一种是将元素包含在当前集中，另一种是将元素排除在当前集之外。通过考虑这两种可能性，我们填充子集。

实施

让我们通过上述方法来看一下拔河问题的实现。

文件名： TugOfWarEx.java

public class TugOfWarEx
{
public int minDiff;

// a utility method that tries each and every solution 
// possible by invoking itself recursively
void TOWUtil(int array[], int size, boolean currElements[],
int noOfSelectedElements, boolean sol[],
int sum, int currSum, int currPosition)
{
// checking whether the currPosition 
// is going out of the bound or not
if (currPosition == size)
{
return;
}

// checking for the numbers of remaining elements
// are not less than the number of elements required
// to construct the solution
if ((size / 2 - noOfSelectedElements) > (size - currPosition))
{
return;
}

// consider the cases when current element
// is not included in the solution
TOWUtil(array, size, currElements, 
noOfSelectedElements, sol, 
sum, currSum, currPosition + 1);

// adding the current element 
// to the solution
noOfSelectedElements = noOfSelectedElements + 1;
currSum = currSum + array[currPosition];
currElements[currPosition] = true;

// checking whether the solution is formed or not
if (noOfSelectedElements == size / 2)
{
// checking whether the solution build is
// better than the best solution found so far
if (Math.abs(sum / 2 - currSum) < minDiff)
{
minDiff = Math.abs(sum / 2 - currSum);
for (int j = 0; j < size; j++)
{
sol[j] = currElements[j];
}
}
}
else
{
// the following recursive call includes the current element
// in the solution
TOWUtil(array, size, currElements,
noOfSelectedElements,
sol, sum, currSum,
currPosition + 1);
}

// removing the current element 
// before returning to the caller  
// of this method
currElements[currPosition] = false;
}

// main method that generates an array
void tugOfWar(int array[])
{
int size = array.length;

// the boolean arrayay that contains the
// inclusion and exclusion of an element
// in current set. The number excluded
// automatically form the other set
boolean[] currElements = new boolean[size];

// The inclusion/exclusion arrayay for
// final solution
boolean[] sol = new boolean[size];

minDiff = Integer.MAX_VALUE;

int sum = 0;
for (int j = 0; j < size; j++)
{
sum = sum + array[j];
currElements[j] = sol[j] = false;
}

// Find the solution using recursive
// function TOWUtil()
TOWUtil(array, size, currElements, 0,
sol, sum, 0, 0);

// Displaying the solution
System.out.print("The elements of the first subset are: ");
for (int j = 0; j < size; j++)
{
if (sol[j] == true)
{
System.out.print(array[j] + " ");
}
}

System.out.print("\n");
System.out.print("The elements of the second subset are: ");
for (int j = 0; j < size; j++)
{
if (sol[j] == false)
{
System.out.print(array[j] + " ");
}
}
}

// Main method
public static void main (String[] argvs)
{
// the input array
int array[] = new int[]{-34, 23, 98, 45, 12, 4, 4, -99, -1, 189, 0};

// computing the size of the input array
int size = array.length; 

// creating an object of the class TugOfWarEx 			
TugOfWarEx obj = new TugOfWarEx();

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(array[i] + " ");
}

System.out.println();

// invoking the method tugOfWar() 
obj.tugOfWar(array);

// updating input array
array = new int[]{-3, 5, 4, 3, 1, 100, 54, 89, 20, 23};

// computing the size of the input array
size = array.length;

System.out.println("\n");

System.out.println("For the array: ");
for(int i = 0; i < size; i++)
{
System.out.print(array[i] + " ");
}

System.out.println();

// invoking the method tugOfWar() 
obj.tugOfWar(array);


}
}

输出

For the array: 
-34 23 98 45 12 4 4 -99 -1 189 0 
The elements of the first subset are: -34 98 45 12 -1 
The elements of the second subset are: 23 4 4 -99 189 0 

For the array: 
-3 5 4 3 1 100 54 89 20 23 
The elements of the first subset are: 4 1 100 20 23 
The elements of the second subset are: -3 5 3 54 89

时间复杂度： 上述程序的 time complexity 为 2ⁿ，其中 n 是数组中元素的数量。

下一主题Java 克隆 HashMap

Java 中的拔河比赛

注意：上面提到的最小差值是指两个子集和之差的绝对值。换句话说，忽略差值的符号，只考虑其大小。

方法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的拔河比赛

注意：上面提到的最小差值是指两个子集和之差的绝对值。换句话说，忽略差值的符号，只考虑其大小。

方法

实施

相关帖子

How to Return an Array in Java

Java 中的类定义

Java 中的套接字编程

Memory Leak in Java

Java 中的 DoubleBuffer clear() 方法及示例

Java 中自动装箱 Integer 对象的比较

如何使用 Java 查找字符串中大写字母、小写字母、数字和特殊字符的百分比

Java 中使用两个栈实现队列

Java &0XFF 示例

Java 中捕获基类和派生类作为异常

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器