1

私は最近、Codeforces で問題を解決しようとしましたが、解決策は正しくありましたが、現在それを証明しようとしています。アルゴリズムは次のようなものです。

最小の割引を最も高価なものに適用し、2 つの連続するより安価なものを無料で使用します。その後、アイテムがなくなるまで続けます。

私はちょっと証明に行き詰まっています。誰かが私に矛盾による正式な証明を与えてくれれば素晴らしいことです.

問題！

4

1 に答える 1

1

それは2つの部分に分かれています：

どの割引を選択しますか?

m最小の割引 ( nitems, n<m)以外の割引 (商品a(1)に対して2 無料) を選択したとします。で商品を購入して無料で入手し、商品を定価で購入して、同じ状況に陥る可能性があります。したがって、最小の割引を選択することは、最悪の場合、他の選択肢と同等です。a(m)bca(1)a(n)bca(n+1)a(m)

どの無料記事を選ぶべきですか?

a1ここで、アイテムにディスカウントを適用しa2、最も高価なものb1の代わりにb2(cost(a1)<cost(b1)またはcost(a2)<cost(b2)) を適用するとします。cost(a1)<cost(a2)ケースが対称であるためと仮定しましょう。次の 3 つのケースが発生します。

  1. どういうわけかa2、プロモーションの一環として無料で手に入れることができます。それなら、a1まだ選んでいない場合でも手に入れることができたはずです.
  2. 割引の一環として、私たちはそれを支払わなければなりません。この割引により、最大で の商品を購入できますc。次のいずれかが発生します。
    • c<=cost(a1): と を交換することができa1ますa2。これにより、他に何も変更せずに、このバスケットのコストが下がります。
    • cost(a2)<=c<cost(a1)d: 電話してみましょう。eこの 2 番目の割引で得られる商品はd、最も高価なものです。最初のディスカウントで無料アイテムとして選択し、2 番目のディスカウントでそれをa2交換して、2 番目のディスカウントで無料アイテムとして選択することで、コストが低くなるか、同等になる可能性があります。da1
  3. 割引価格で購入しました。他に何も変更せずに、より低いコストで選択a2して支払うことができたので、選択は最適ではありませんでした。a1a1
于 2013-01-14T11:06:56.243 に答える