2

私はMatlabを使用してコードに取り組んでおり、参照リストのすべての要素をカバーするために必要な最小数のリスト(特定のリストのセット)を見つける必要があります。

たとえば、私の参照リストが

X = [0 1 2 3 4 5 6 7 8 9]

そして、次のような一連のリストがあります。

A = [0 1 3 5 6 7 9]
B = [0 1 2 3 4]
C = [5 6 7 8 9]
D = [1 2 3 4]
E = [1 5 7 8]

のすべての要素をカバーするために必要なリストの最小数Xは2(BとC) ですが、最初に最も多くの要素 ( A) をカバーするリストのみを検索し、残りの要素をカバーする他のリストを見つけようとすると、少なくとも3リストを使用することになります。これに必要な最小数のリストを検索できるコードを作成する最良の方法は何でしょうか (これにより、Bandの出力が得られますC)。どんな助けでも大歓迎です...この問題への最善のアプローチ方法の概念的な説明(実際のコードではない)だけでも、大きな助けになります!

4

2 に答える 2

1

AmroによるDev-iLの最初のアプローチと同様のソリューション：

function varargout = q36323802A
R = [0 1 2 3 4 5 6 7 8 9];

names = {'A' 'B' 'C' 'D' 'E'};
L = {...
    [0 1 3 5 6 7 9]
    [0 1 2 3 4]
    [5 6 7 8 9]
    [1 2 3 4]
    [1 5 7 8]
};
N = numel(L);

%// powerset of L: set of all subsets (excluding empty set)
powerset = cell(1,N);
for k=1:N
    sets = nchoosek(1:N, k);
    powerset{k} = num2cell(sets,2);
end
powerset = cat(1, powerset{:});

%// for each possible subset, check if it covers the target R
mask = false(size(powerset));
for i=1:numel(powerset)
    elems = unique([L{powerset{i}}]);
    mask(i) = all(ismember(R, elems));
end
if ~any(mask), error('cant cover target'); end

%// from candidates, choose the one with least amount of sets
candidates = powerset(mask);
len = cellfun(@numel, candidates);
[~,idx] = min(len);
out = candidates{idx};
varargout{1} = names(out);
于 2016-03-31T16:23:22.557 に答える