Поиск всех возможных перестановок с ограничением суммы и опцией избыточности? (MATLAB)

Question

У меня была следующая проблема:

Существует гипотетический почитаемый музыкант, вышедший на пенсию. Музыкант время от времени получает гонорары за свои прошлые записи. Музыкант чека роялти всегда бывает, как:

$ 1, $ 5, $ 8, $ 12, $ 17, $ 20, $ 42, $ 100, или $ 200

Это означает, что музыкант получает только роялти чеки в количествах, указанных выше. Мне было интересно, как мне вычислить общее количество возможных способов, которыми музыкант может получить деньги, чтобы накопить 1000 долларов? В этой задаче есть некоторые ограничения/допущенные допущения. Это:

(1) Нет крышки на общую сумму «чеков», которую может получить музыкант, чтобы получить 1000 долларов США. Например, музыкант может получить 1 000 $ 1 чеков, 5 $ 200 чеков или 10 $ 20 чеков и 4 $ 200 чеков и т. Д. И т. Д.

(2) Как следует из (1), вы можете получить кратные любые проверки (в факт, сумма всех сингулярных опций проверки составляет 405 долларов США, что делает это условие необходимым для накопления 1000 долларов США).

(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 чеков. Помните, что музыкант получает платные чеки «время от времени», поэтому порядок приема чек делает возможным различные решения (перестановки).

Мне интересно найти только общее количество решений для решения этой проблемы с заданными возможностями проверки, а не распечатывать их.

Это мой подход, до сих пор:

• Определить переменные, которые представляют возможности проверки (. Ех х1 = 1, х2 = 5, х3 = 8, и т.д. и т.п.)

• Включайте некоторые, если-то заявление, которое проверяет, если множество кратных x1, x2, x3 ... хп равна 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?