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

Question

我想到了以下问题:

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

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

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

(1) 音乐家为获得 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 是不同的“解决方案”，后者也是不同的“解决方案”而不是 $200、$100、$100、$200、$100、$100、$100 和 $100，尽管这两种解决方案都包含 6 张 100 美元的支票和 2 张 200 美元的支票。请记住，音乐家“不时”收到支票，因此支票接收的顺序会导致不同解决方案(排列)的可能性。

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

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

• 定义表示检查可能性的变量(例如 x1 = 1、x2=5、x3 = 8 等)

• 合并一些 if-then 语句来检查一组 x1、x2、x3...xn 的倍数是否等于 1000

• 如果是，则将某个计数器变量加 1

• 一旦所有迭代都用完/任何循环边界完成，显示计数器值。

但是，我不知道如何将 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

您可以手动完成，创建一个表(变量 M)，其中包含值(汇总)和获得该值的可能性数。对于您可以直接通过检查获得的每个值，用 1 种可能性对其进行初始化。

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

• 从表中弹出第一个条目(最小值)。将它与每张支票(使用一次)重新组合，然后重新插入到表格中。
• 当组合值已在表中时，将数字相加。
• 当组合值不在表中时，插入一个新条目。

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