排列数字组以适合特定大小的总计 [英] Arranging group of numbers to fit Specific size total

问题描述

我在一个小组中有几个不同的数字，大小各不相同，我想根据小组的最大人数来计算数字应该进入哪个小组.

I have several different numbers in a group that range in sizes and would like to calculate which group the numbers should go in based on the max size the group can be.

数字示例:10,20,30,40,50,60

Example of the numbers: 10,20,30,40,50,60

条件示例:一个组中可累加的最大总数 是60

Example of conditions: the maximum total the numbers can add up to in a group is 60

因此，在上面的示例中，答案是:

So from the example above the answer would be:

第1组的数字为10、20、30

group 1 would have the numbers 10,20,30

第2组的数字为40

第3组的数字为50

第4组的数字为60

在matlab/octave或excel/librecalc中是否可以计算?

Is there a way in matlab/octave or excel/librecalc this can be computed?

PS:一个组也可以有40和20，该组的总数不能超过60.但是每个号只能使用一次.

PS: A group can also have the number 40 and 20 the group total just can't go over 60. But they can only use each number once.

有数学术语吗?

推荐答案

下面的解决方案使用蛮力方法来生成Powerset的 powersets (尽管已修剪) .然后检查是否满足设置的条件的组(即，将所有数字分为几组，以使任何组的总和都不超过60).我从 PMTK3 工具箱.

The solution below uses a brute-force approach to generating powersets of powersets (although trimmed). Then checks for groups that satisfy the conditions set (namely divide all the numbers into groups such that no group contain a sum of more than 60). I borrowed some code from the powerset.m function in PMTK3 toolbox.

这对于像这样的小问题应该可以正常工作，但是我怀疑对于较大的输入，它的大小将成倍增长.我确定那里有更好的启发式/算法，所以以此作为起点...

This should work fine for a small problem like this one, but I suspect it would grow exponentially in size for larger input. I'm sure there are better heuristic/algorithms out there, so take this as a starting point...

%# set of numbers
S = [10,20,30,40,50,60];

%# powerset of S (exclude empty set)
b = (dec2bin(2^numel(S)-1:-1:1) == '1');
P = cellfun(@(idx)S(idx), num2cell(b,2), 'UniformOutput',false);

%# keep only sets where the sum is at most 60
P = P(cellfun(@sum,P) <= 60);

%# take the powerset of the powerset, although we can
%# reduce it to no more than numel(S) subsets in each.
%# The idea here is: nchoosek(p,1:numel(s))
b = (dec2bin(2^numel(P)-1:-1:1) == '1');
b = b(sum(b,2)<=numel(S),:);
PP = cellfun(@(idx)P(idx), num2cell(b,2), 'UniformOutput',false);

%# condition: every number appears exactly once in groups
ppp = cellfun(@(x) [x{:}], PP, 'UniformOutput',false);
idx = find(cellfun(@numel,ppp) == numel(S));
idx2 = ismember(sort(cell2mat(ppp(idx)),2), S, 'rows');
PP = PP( idx(idx2) );

%# cleanup, and show result
clearvars -except S PP
celldisp(PP)

这给了我12个解决方案.例如:

This gave me 12 solutions. For example:

>> PP{1}{:}
ans =
    10    20    30
ans =
    40
ans =
    50
ans =
    60

>> PP{6}{:}
ans =
    10    40
ans =
    20
ans =
    30
ans =
    50
ans =
    60

>> PP{12}{:}
ans =
    10
ans =
    20
ans =
    30
ans =
    40
ans =
    50
ans =
    60

这篇关于排列数字组以适合特定大小的总计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！