使用总和约束和冗余选项查找所有可能的排列？ (MATLAB)

Question

我想到了以下问题：

假设有一位退休的受人尊敬的音乐家。音乐家会不时收到他们过去录音的版税支票。音乐家的版税支票总是以：

1 美元、5 美元、8 美元、12 美元、17 美元、20 美元、42 美元、100 美元或 200 美元

这意味着音乐家只能收到上述金额的版税支票。我想知道，我将如何计算音乐家获得报酬以积累 1,000 美元的可能方式总数？这个问题有一些constraints/allowed假设。它们是：

(1) "checks" 音乐家可以获得 1,000 美元的总金额没有上限。例如，音乐家可以收到 1,000 张 1 美元的支票、5 张 200 美元的支票，或者 10 张 20 美元的支票和 4 张 200 美元的支票，等等

(2) 正如 (1) 所暗示的，您可以收到任何支票的倍数（事实上，所有单支票选项的总和为 405 美元，这使得积累 1,000 美元成为必要条件）。

(3) 订单很重要。获得报酬 $200、$200、$100、$100、$100、$100、$100 和 $100 与 $100、$100、$100、$100、$100、$100、$200 和 $200 是不同的"solution"，后者也是不同的"solution" 而不是 $200、$100、$100、$200、$100、$100、$100 和 $100，即使这两个解决方案都包含 6 张 100 美元的支票和 2 张 200 美元的支票。请记住，音乐家会收到支票 "from time to time"，因此支票接收的顺序会导致不同解决方案（排列）的可能性。

我感兴趣的是在给定的检查可能性下仅找到解决此问题的解决方案总数，而不是将它们打印出来。

到目前为止，这是我的方法：

定义表示检查可能性的变量（例如 x1 = 1、x2=5、x3 = 8 等）
合并一些 if-then 语句，检查一组 x1、x2、x3...xn 的倍数是否等于 1000
如果是，则将某个计数器变量加 1
一旦所有迭代 exhausted/any 循环边界完成，显示计数器值。

但是，我不知道如何将 x1、x2、x3 及其排列组合到给定方程中，也不知道如何求解此类方程。

Answer 1

这是我的解决思路，遵循动态规划的模式：

checks=[1,5,8,12,17,20,42,100,200];
target=300;
M=[checks;ones(size(checks))];
while M(1,1)<target
    %we know that there are #possibilities to get a sum of value
    value=M(1,1);
    possibilities=M(2,1);
    M(:,1)=[];
    disp(value)
    %combine value with each check:
    for idx=1:numel(checks)
        if value+checks(idx)<=target
            ii=find(M(1,:)==value+checks(idx),1,'first');
            if isempty(ii)
                M(:,end+1)=[value+checks(idx),possibilities];
            else
                M(2,ii)=M(2,ii)+possibilities;
            end
        end
    end
    %Sort M by value
    [a,idx]=sort(M(1,:));
    M=M(:,idx);
end

您可以手动完成，创建一个 table（变量 M），其中包含值（汇总）和获得该值的可能性。为每个可以直接通过检查获得的值初始化为 1 种可能性。

现在重复直到你得到你想要的值：

从 table（最小值）中弹出您的第一个条目。将它与每个检查（使用一次）重新组合并将其重新插入到 table.
当合并值已经在table中时，将数字求和。
当组合值不在 table 中时，插入一个新条目。

虽然在理论上这种方法是精确的，但它很快就超过了浮点精度。对于目标值 300，结果是 ~10^42，超过了浮点精度。符号工具箱是否可用，那么您可以切换到vpa吗？

使用总和约束和冗余选项查找所有可能的排列？ (MATLAB)

Finding all possible permutations with a sum constraint and a redundancy option? (MATLAB)

algorithm

matlab

constraints

permutation