3

产品 A 成本 10 美元，B 成本 3 美元，C 成本 0.50 美元。一个人花 100 美元买了 100 件物品。该人购买了每种物品的数量。

我找到了答案——

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

但是我无法在 java 中实现它作为我从 Hit and Trial 中得到结果的解决方案。解决这个问题的算法是什么

4

4 回答 4

8

普通的蛮力：

   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 个总量 - 很好（并且从编码所需的时间点来看是最佳的）。

于 2012-04-06T04:01:29.567 回答
2

你需要实现你的算法来解决这两个方程

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

由(2)，我们可以得出：

C = 100 - A - B

将此信息代入 (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。

继续以这种方式求解方程，并将 A、B 和 C 替换为 Java 变量，您将能够提供解决方案。

于 2012-04-06T04:11:00.853 回答
1

这两种解决方案都很容易找到。Ring Bearer 已经给出了几乎所有的方法。环承载结束于：

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

A 只有两个值满足这一点：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).
}
于 2012-04-06T04:30:24.373 回答
0

这是背包问题的变体，您可以寻找基于动态规划的解决方案，该解决方案比蛮力（在计算复杂性方面）要好。一个简单的搜索产生了这样的链接

于 2012-04-06T04:09:52.293 回答