อัลกอริทึม Tug of War (การแบ่งทีมดึงเชือก)

บทนำ

กำหนดชุดจำนวนเต็ม ต้องแบ่งเป็น 2 ส่วนให้ผลต่างของผลรวมทั้งสองส่วนน้อยที่สุด กล่าวคือแบ่งทีมให้มีแรงใกล้เคียงกันมากที่สุดสำหรับเกมดึงเชือก

ถ้าจำนวน n เป็นคู่ แบ่งเป็น n/2 แต่ถ้าเป็นคี่ ส่วนหนึ่งเป็น (n-1)/2 อีกส่วนเป็น (n+1)/2

อินพุตและเอาต์พุต

Input: เซตน้ำหนัก {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}
Output: Left: {45, -34, 12, 98, -1}
        Right: {23, 0, -99, 4, 189, 4}

อัลกอริทึม

tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos)

Input: เซตน้ำหนัก, จำนวน, รายการปัจจุบัน, จำนวนที่เลือก, โซลูชัน, ความต่าง, ผลรวมทั้งหมด, ผลรวมในเซต, ตำแหน่ง
Output: เซตโซลูชันสำหรับทีมซ้ายและขวา

Begin
    if pos = n then return
    if (n/2 - select) > (n - pos) then return
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    select := select + 1
    total := total + weight[pos]
    curr[pos] := true  // เลือก item ที่ pos
    if select = n/2 then
        if |sum/2 - total| < diff then
            diff := |sum/2 - total|
            for i := 0 ถึง n do sol[i] := curr[i] done
    else
        tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1)
    curr[pos] := false  // ย้อนกลับ
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include<cmath>
using namespace std;

void tugOfWar(int* weight, int n, bool curr[], int select, bool sol[], int &diff, int sum, int total, int pos) {
    if (pos == n) return;
    if ((n/2 - select) > (n - pos)) return;
    tugOfWar(weight, n, curr, select, sol, diff, sum, total, pos+1);
    select++;
    total += weight[pos];
    curr[pos] = true;
    if (select == n/2) {
        if (abs(sum/2 - total) < diff) {
            diff = abs(sum/2 - total);
            for (int i = 0; i

ผลลัพธ์
Left: 45 -34 12 98 -1
Right: 23 0 -99 4 189 4