所有可能的組合

Question

我有一個數學問題如下：

我有一個容器總共容納21000公斤。 我有4個項目A，B，C，D。

項目A重量1千克。 B項重量4公斤。 C項重量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

這與SICP的「Counting Change」示例非常相似。請參閱：

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

實例：計數變化

Answer 2

你必須解決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所有可能的值。