Js分组用户均等分配算法

Question

给定n个具有v值的用户，将用户分为g组，使每组用户的值之和的值相似，每组的用户数必须等于a的最大差异用户：

    const users = [
       { name: 'a', value: 1 },
       { name: 'b', value: 2 },
       { name: 'c', value: 3 },
       { name: 'd', value: 4 },
       { name: 'e', value: 5 },
       { name: 'f', value: 6 },
       { name: 'g', value: 7 },
       { name: 'h', value: 8 },
       { name: 'i', value: 9 }
    ];
    
    const numGroups = 3;
    const groupedUsers = divideUsersIntoGroups(users, numGroups);
    
const result = [
    [
        users: [{
            name: 'a',
            value: 1
        }, {
            name: 'e',
            value: 5
        }, {
            name: 'i',
            value: 9
        }]
        valueTot: 15
    ],
    [
        users: [{
            name: 'b',
            value: 2
        }, {
            name: 'f',
            value: 6
        }, {
            name: 'g',
            value: 7
        }]
        valueTot: 15
    ],
    [
        users: [{
            name: 'c',
            value: 3
        }, {
            name: 'd',
            value: 4
        }, {
            name: 'h',
            value: 8
        }]
        valueTot: 15
    ]
];

我正在使用以下算法，但没有得到所需的结果。

function divideUsersIntoGroups(users, numGroups) {
users.sort((a, b) => a.value - b.value);

const groupedUsers = Array.from({ length: numGroups }, () => []);

users.forEach((user, index) => {
const groupIndex = index % numGroups;
groupedUsers[groupIndex].push(user);
});

return groupedUsers;
}

或者

function divideUsersIntoGroups(users, numGroups) {
    // Step 1: Calculate the total sum of values in the users list
    const totalSum = users.reduce((acc, user) => acc + user.value, 0);

    // Step 2: Determine the target sum for each group
    const targetSum = totalSum / numGroups;

    // Step 3: Sort the users list based on their values
    users.sort((a, b) => a.value - b.value);

    // Step 4: Initialize an array to store the groups
    const groupedUsers = Array.from({ length: numGroups }, () => ({ users: [], valueTot: 0 }));

    // Step 5 & 6: Assign users to groups based on closest total value to target sum
    users.forEach(user => {
        let minDiff = Infinity;
        let bestGroupIndex = 0;

        groupedUsers.forEach((group, index) => {
            const currentDiff = Math.abs(group.valueTot + user.value - targetSum);
            if (currentDiff < minDiff) {
                minDiff = currentDiff;
                bestGroupIndex = index;
            }
        });

        groupedUsers[bestGroupIndex].users.push(user);
        groupedUsers[bestGroupIndex].valueTot += user.value;
    });

    return groupedUsers;
}

Answer 1

您可以通过检查所有可能的组合来采取暴力方法。

function subset(values, groups, sum) {
    function iter(left, right, index = 0) {
        const
            add = (a, b) => a + b,
            total = a => a.reduce(add, 0);
            
        if (!left.length) {
            if (right.every(a => a.length === 3 && total(a) === sum)) result.push(right);
            return;
        }
        
        for (let i = 0; i < groups; i++) {
            const
                subArray = [...right[i], left[0]];
                
            if (total(subArray) > sum) continue;
            iter(left.slice(1), Object.assign([], right, { [i]: subArray }));
        }
    }
    const result = [];
    iter(values, Array.from({ length: groups }, _ => []));
    return result;
}

console.log(subset([9, 8, 7, 6, 5, 4, 3, 2, 1,], 3, 15));

.as-console-wrapper { max-height: 100% !important; top: 0; }