2

让我们考虑我们有一个向量VEC。

有没有办法找到可以对哪些向量元素进行分组，以便它们在 MATLAB 中总和为给定的数字 NUM？

例如，如果VEC = [2 5 7 10]和NUM = 17

请求的算法应该提供子向量[2 5 10]和[7 10]总和的答案给定NUM。

4

3 回答 3

3

这是解决此问题的一种方法conbntns，它是 Mapping Toolbox 中的一个函数，用于检索值集的所有可能组合（如果您没有此工具箱，则可以使用FEX 中的组合器）。因此，例如对于 vector A，我们将找到给定长度（1 到 的长度A）的所有可能组合，然后将它们相加，看看哪个等于NUM=17：

NUM=17;
A=[2 5 7 10];
for ii=1:numel(A)
    B=combntns(A,ii);
    C=sum(B,2);
    D=find(C==NUM);
    if ~isempty(D)
        B(D,:)
    end
end

ans =
     7    10
ans =
     2     5    10

当然，您可以将B(D,:)输出存储到单元格数组或其他任何内容中以供将来使用...

于 2013-02-13T08:19:08.320 回答
3

这是另一种无需任何工具箱或第三方功能的方法。它逐步检查所有可能的值组合VEC并测试总和是否等于NUM。

VEC = [2 5 7 10]
NUM = 17;
n = length(VEC);
for i = 1:(2^n - 1)
    ndx = dec2bin(i,n) == '1';
    if sum(VEC(ndx)) == NUM
        VEC(ndx)
    end
end

ans =
     7    10
ans =
     2     5    10

这类似于natan 的答案，但没有使用conbntns.

于 2013-02-13T14:46:23.480 回答
2

如果我没记错的话，这个问题是 NP 难的。
但是一个有趣的方法可能是使用bintprog：

n = numel( VEC );
x0 = zeros( 1, n ); % one possible init guess
x = bintprog( zeros( n, 1 ), ...  % objective function meaningless, we look for feasibility
              [], [], ... % no inequality constraints
              VEC(:)', NUM, ... %' we want the sum of selected elements to equal NUM
              x0 ); % changing init x0 might result with different solutions
find( x )

二元向量x（ 中的优化解bintprog）选择总和为的相关元素NUM

于 2013-02-13T08:37:45.707 回答