4

假设我在 A 中有 7 个项目，在 B 中有 4 个项目

A=[10;40;90;130;200;260;320]
B=[100;300;500;1000]

我想要列出可能的组合，其中：

  • 必须包含A 的所有子组件
  • 可以添加 B 的子组件，直到添加的所有子组件的总和大于 2000

任何人都知道如何在 Matlab 中做到这一点？

我的尝试：

X=sum(A);
y=1;
for Y=1:((length(A))-1);
   X=X+B(y);
   if(X>2000)
       disp('Following is unacceptable')    
   end
   y=y+1
end

但是，此代码不正确。它只是添加 B 的第一个元素，然后将其添加到第二个元素，依此类推。它没有为我提供可能的组合。

例子 ：

  • 总和（A）+ B（1）=确定
  • 总和（A）+ B（4）=不正确
  • 总和（A）+ B（1）+ B（2）=确定
  • 总和（A）+ B（2）+ B（3）=确定
  • ETC...

如果将来 A 或 B 的值发生变化，我希望这可以自动化。我不确定这是否也是概率的情况。

4

3 回答 3

4

只需使用nchoosekand 一个双for循环来遍历所有可能的元素组合B：

SA = sum(A);
for k = 1:numel(B)
    for idx = nchoosek(1:numel(B), k)'
        B_subset = B(idx);
        if (SA + sum(B_subset) <= 2000)
            disp([A(:)', B_subset(:)'])
        end
    end
end

这将打印总和小于（或等于）2000 的所有组合。对于您的示例，我们得到：

    10    40    90   130   200   260   320   100
    10    40    90   130   200   260   320   300
    10    40    90   130   200   260   320   500
    10    40    90   130   200   260   320   100   300
    10    40    90   130   200   260   320   100   500
    10    40    90   130   200   260   320   300   500
    10    40    90   130   200   260   320   100   300   500

解释：

内部for循环：
内部for循环使用nchoosek(1:numel(B), k)，它从 1...length(B) 生成所有 k 长度组合（我使用它numel而不是length出于习惯；在这种情况下，它具有相同的效果）。例如，在我们的例子B中有 4 个元素，所以k = 3我们得到nchoosek(1:4, 3)：

    1   2   3
    1   2   4
    1   3   4
    2   3   4

我们从中得到的是 中元素索引的所有可能的 k 长度组合B。在每次迭代中，此循环for将不同的索引组合分配给idx. 我们如何将索引转换B为真实元素？我们简单地写B(idx)。
在循环内部测试组合：如果总数sum(A) + sum(B(idx))小于（或等于）2000，则显示该组合。

外for循环：
外for循环简单地迭代所有可能的组合长度（即，遍历所有可能的值k）。

希望有帮助！

PS：

未来的一些 MATLAB 编程技巧：
1. 变量名区分大小写。
2. 你不需要增加循环变量。for循环会自动为您执行此操作。

于 2012-11-20T22:47:39.040 回答
2

假设 B 不是很长（大约 10 个元素），对所有组合进行详尽搜索就可以了。您可以使用递归函数执行这种详尽的搜索，但下面的代码使用了一个在 MATLAB 中特别简洁的技巧：它通过将每个组合表示为二进制位字符串来扫描 B 元素的所有组合。

% examine each of 2^length(B) combinations
for i=0:2^length(B)-1
    % converts the binary string into an array of 0 and 1 used to select elements in B
    combo = dec2bin(i, length(B))-'0'; 
    % print the combination of elements if their sum is large
    if combo * B + sum(A) > 2000
       disp(find(combo));
    end
end

有 2^length(B) 种可能的组合。这会依次检查它们，将组合表示为长度为 length(B) 的二进制字符串，并评估这些元素的总和（位串和 B 之间的点积）。

于 2012-11-20T22:36:24.617 回答
2

最好的方法将涉及一些递归，如下所示：

sumA=sum(A);
find_CombinationsOfB(B,sumA,[])

function ret=findCombinationsOfB(in_vals,total_sum,already_contained)

if total_sum>2000
    ret=false;
else
    for y=1:length(in_vals);
       if (~findCombinationsOfB(in_vals([1:(y-1);(y+1):length(in_vals)],total_sum+in_vals(y),[already_contained in_vals(y))
          display([already_contained in_vals])
       end
    end
    ret=true;
end

本质上，它的作用是尝试 B 的每种组合。它将打印任何不等于 2000 的组合，包括来自 A 的总和。

一步一步，这是它的作用：

  1. 最初，传递 B 的完整数组以及 A 的总和。传递一个空数组以存储迄今为止已使用 B 的哪些元素。
  2. 每个元素依次添加到函数中，并使用新的总和再次调用，并且数组中缺少一个值。
  3. 如果在任何时候数组总和超过 2000，它就会停止推理链。

如果您想了解更多关于它是如何工作的，请在函数的开头打印 in_vals、total_sum 和 already_contained，如下所示：

fprintf("in_vals=%s   total_sum=%i   already_contained=%s",mat2str(in_vals),total_sum,mat2str(already_contained));

它应该在每次迭代中向您展示正在发生的事情。

于 2012-11-20T22:42:44.377 回答