все возможные комбинации

Question

У меня есть математическая задача, которая выглядит следующим образом:

У меня есть контейнер, который вмещает 21000 кг. У меня есть 4 предмета A, B, C, D.

Предмет А весит 1 кг. Вес изделия B - 4 кг. Элемент С весом 5 кг. Вес изделия D также составляет 5 кг.

Я ищу алгоритм, который будет перебирать все возможные комбинации, сохраняя вышеприведенное уравнение. например:

{20000, 0, 0, 200} -> 20000 * 1 + 0 * 4 + 0 * 5 + 200 * 5 = 21000 кг.

{19996, 1, 0, 200} -> 19996 * 1 + 1 * 4 + 0 * 5 + 200 * 5 = 21000 кг.

Answer 1

Вы должны решить a + 4b + 5c + 5d = 20000 (a,b,c,d >=0)

или a + 4b = 2000 - 5e = 5(400-e), где e = c + d

, поэтому a + 4b может быть 0, 5, 10, 15, 20, ..., 2000

, вы можете легко найти всевозможные значения a и b сверху

, после этого вы узнаете значение e = c + d, оттуда вы можете легко найти все возможные значения c и d.

Answer 2

Это очень похоже на пример "Подсчета изменений" из SICP.См .:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2

Пример: подсчет изменений