5

昨日スーパーマーケットの売り場に立って以来、私の後ろのせっかちで神経質な列を無視しようとしながら、コインの最適な配分をヒューリスティックに見つけようとして、根本的なアルゴリズムの問​​題について考えていました。

値が v 1 ,...,v nのコイン システムが与えられ、限られたコインのストック a 1 ,...,a nと、支払う必要のある合計 s が与えられます。パーティション x 1 ,...,x n (with 0<=x i <=a i ) を x 1 *v 1 +x 2 *v 2 +...+xで計算するアルゴリズムを探しています。n *v n >= s x 1 +...+x n - R(r) の合計が最大になるようにします。ここで、r は変化です。つまり、r = x 1 *v 1 +x 2 *v 2 + です。 ..+xn *v n - s であり、R(r) はレジ係から返されたコインの数です。レジ係はすべてのコインの量に制限がなく、常に最小数のコインを返すと仮定します (たとえば、SCHOENING et al. で説明されている欲張りアルゴリズムを使用して)。また、お金の変更がないことを確認する必要もあります。そのため、最善の解決策は、単純にすべてのお金を提供することではありません (その場合、解決策は常に最適であるため)。

クリエイティブなご意見ありがとうございます。

4

1 に答える 1

1

私の理解が正しければ、これは基本的にサブセット sumの変形です。a[i] = 1各コインを 1 つずつ ( for each )持っていると仮定するとi、次のように解決します。

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
        sum[j] |= sum[j - v[i]]

次に、最初のk >= sandsum[k]を見つけますtrue。どのコインがそれぞれに貢献したかを追跡することで、実際に使用されたコインを取得できますsum[j]。sコインを使用して合計を得ることができるほど、変更は少なくなります。これがあなたが求めているものです。

これで、各コインを 1 つずつ持っているのではなく、各コインをi持っています。私はこれを提案します：a[i]i

sum[0] = true
for i = 1 to n do
    for j = maxSum downto v[i] do
       for k = 1 to a[i] do
           if j - k*v[i] >= 0 do
               sum[j] |= sum[j - k*v[i]] <- use coin i k times

xこれからベクトルを取得するのはかなり簡単なはずです。詳細が必要な場合はお知らせください。

于 2011-02-09T23:55:13.300 に答える