3

製品Aの価格は10ドル、Bの価格は3ドル、Cの価格は0.50ドルです。ある人が100個のアイテムを100ドルで購入しました。その人が購入した各アイテムの数。

私は答えを見つけました-

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

しかし、Hit and Trialの結果を得たソリューションとして、Javaで実装することはできません。この問題を解決するためのアルゴリズムは何になりますか

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");

        }
    }

2つの答えを与えます：

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

PSもちろん、これは最適なソリューションではありませんが、3つのアイテムと合計100の量で問題ありません（コーディングに必要な時点から最適です）。

于 2012-04-06T04:01:29.567 に答える
2

これらの 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

どちらのソリューションも非常に簡単に見つけることができます。リングベアラーは、これを行う方法のほぼすべてをすでに提供しています。リングベアラーは次で終了しました：

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 の 2 つだけです。すべての解をすばやく見つけるには、次のようにします。

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 に答える