製品Aの価格は10ドル、Bの価格は3ドル、Cの価格は0.50ドルです。ある人が100個のアイテムを100ドルで購入しました。その人が購入した各アイテムの数。
私は答えを見つけました-
94 * 0.5 = 47
1 * 3 = 3
5 * 10 = 50
しかし、Hit and Trialの結果を得たソリューションとして、Javaで実装することはできません。この問題を解決するためのアルゴリズムは何になりますか
単純なブルートフォース:
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つの答えを与えます:
PSもちろん、これは最適なソリューションではありませんが、3つのアイテムと合計100の量で問題ありません(コーディングに必要な時点から最適です)。
これらの 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 変数に置き換えると、解が得られます。
どちらのソリューションも非常に簡単に見つけることができます。リングベアラーは、これを行う方法のほぼすべてをすでに提供しています。リングベアラーは次で終了しました:
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).
}
これはナップザック問題の変形であり、動的計画法ベースのソリューションを探すことができます。これは、 (計算の複雑さの点で) 総当たりよりも優れている可能性があります。簡単な検索でこのようなリンクが得られました