算法为每个项目

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). 
}