0

グループ内にサイズの範囲があるいくつかの異なる数字があり、グループの最大サイズに基づいて数字がどのグループに入る必要があるかを計算したいと考えています。

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

条件の例: グループ内で合計できる数の最大合計は 60 です

したがって、上記の例からの答えは次のようになります。

グループ 1 の数字は 10、20、30 になります。

グループ 2 の番号は 40 になります。

グループ 3 の番号は 50 になります。

グループ 4 の番号は 60 になります。

これを計算できるmatlab/octaveまたはexcel/librecalcの方法はありますか?

PS: グループは 40 と 20 の番号を持つこともできますが、グループの合計は 60 を超えることはできません。ただし、各番号は 1 回しか使用できません。

これに使用される数学用語はありますか？

4

1 に答える 1

1

編集：

以下のソリューションでは、パワーセットのパワーセットを生成するために力ずくのアプローチを使用します(トリムされますが)。次に、条件セットを満たすグループをチェックします (つまり、グループの合計が 60 を超えないように、すべての数値をグループに分割します)。PMTK3powerset.mツールボックスの関数からいくつかのコードを借りました。

これは、このような小さな問題では問題なく機能するはずですが、入力が大きくなると指数関数的にサイズが大きくなると思います。より良いヒューリスティック/アルゴリズムがあると確信しているので、これを出発点としてください...

%# 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のソリューションが得られました。例えば：

>> 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
于 2012-06-08T15:55:46.860 に答える