算法爲每個項目

Question

產品A成本10美元，B成本3美元和C成本0.50美元。 一個人以100美元購買了100件物品。每個人購買的物品有多少。

我找到了答案原樣

94 * 0.5 = 47 
1 * 3 = 3  
5 * 10 = 50 

但我沒能實現它在Java中，我得到了命中和審判結果的解決方案。 會有什麼算法用於解決該問題

Answer 1

平原蠻力：

for (int i1 = 0; i1 <= 10; i1++) { 
     for (int i2 = 0; i2 < 34; i2++) { 
      int i3 = 100 - i2 - i1; 
      int total = i1 * 10 + i2 * 3 + i3/2; 
      if (total == 100 && i3 % 2 == 0) 
       System.out.println(i1 + " * 10 + " + i2 
         + " * 3 + " + i3 + " * 0.5 = 100"); 

     } 
    } 

給出兩個答案：

• 0 * 10 + 20 * 3 + 80 * 0.5 = 100
• 5 * 10 + 1 * 3 + 94 * 0.5 = 100

PS當然，這不是最佳的解決方案，但只有三個項目和100個總量 - 這很好（從編碼所需的時間點來看是最優的）。

Answer 2

這是knapsack problem的變體，您可以查找基於dynamic-programming的解決方案，該解決方案比蠻力（計算複雜性）要好。一個簡單的搜索得到的鏈接像this

Answer 3

你需要實現你的算法求解這兩個等式

A + B + C = 100 -----------(1) 
10A + 3B + 0.5C = 100 -----------(2) 

由式（2），我們可以計算出的是：

C = 100 - A - B 

Substitue此信息（2）

10A + 3B + 0.5 * (100 - A - B) = 100 
This reduces to 
19A + 5B = 100 

然後你可以扣除：

B = 20 - (19A/5) 

現在，試着找出（使用一個int環）的A什麼是「整體」的價值，將B成爲一個整體值（通常這樣的問題，你總是買整個商品般的水果沒有分數）

你會發現當A = 5時，B = 1。

繼續用這種方法解決方程式，並用Java變量替換A，B和C，您將能夠提供解決方案。

Answer 4

這兩種解決方案都很容易找到。戒指持票人已經給出了幾乎所有的這種做法。環承載結束了：

B = 20 - (19A/5) 

我們知道別的東西，但：

A, B, and C are all non-negative integer values. 

這意味着19A/5必須是：（1）一個整數（否則B將不會是一個整數）， （2）最多20（否則B將爲負）。這意味着對於（1），A必須是5的倍數，並且對於（2），A必須至多是5。

還要注意的是，要求19A/5 < = 20可以作爲被改寫：

19A <= 100 

存在用於滿足這兩個值：0和5一個非常快速的方式找到所有解決方案那麼將會這樣做：

for (A = 0; 19*A <= 100; A += 5) 
{ 
    // Show the solution for this value of A (with B = 20 - 19A/5 and C = 100 - A - B). 
}