0

この質問 (最後の質問) は、Benelux Algorithm Programming Contest-2007 に掲載されました。

http://www.cs.duke.edu/courses/cps149s/spring08/problems/bapc07/allprobs.pdf

問題文の要約:

企業は、利益を最大化するために、特定の入力に対していつ購入するか、販売するか、または何もしないかの戦略を立てる必要があります。入力は次の形式です。

6
4  4  2
2  9  3
....
....

これは、入力が 6 日間与えられることを意味します。

1 日目: 4 株を取得します。それぞれの価格は 4 ドルで、最大で 2 株を売却できます
。2 日目: 2 株を取得し、それぞれの価格は 9 ドルで、最大で 3 株を売却でき
ます

達成できる最大の利益を出す必要があります。

この問題をどうしようか考え中です。力ずくでやると時間がかかりすぎる気がします。これを 0-1 ナップサックのような DP の問題に変換できるとしたら? いくつかの助けをいただければ幸いです。

4

3 に答える 3

0

その日にできる限りの株数を最高値で売るしかないので、(これは(効率的に)実行するのは少し難しいかもしれません)と考えていました。

アルゴリズムの効率を改善するために、これまでに受け取ったシェアの合計数を毎日計算することをお勧めします。

価格の降順で日を処理します。

1 日sell amount = min(daily sell limit, shares available)(最大価格日 (最初に処理された日) の場合、利用可能な株数 = 現在までに受け取った株数)。

以降のすべての日については、shares available -= sell amount. (shares available - shares sold)前日については、その日と処理された日の間のすべてのエントリ = 0をバイナリ検索します。

値を物理的に設定する必要はないかもしれません (少なくともすべてのステップではありません)。これまでの履歴からその場で計算するだけです (インターバル ツリーなどを考えています)。

于 2013-01-03T23:21:18.197 に答える
0

DPで解決できる

日数が n 日で、株式の総数が m であるとします。

f[i][j] は、i 日目に j 株が残っている場合、最大利益が f[i][j] であることを意味します。

明らかに、f[i][j]=maximum(f[i-1][j+k]+k*1日あたりの価格[i])、0<=k<=最大株数販売[i]

f[i][...] は f[i-1][...] のみに依存するため、ローリング配列をここで使用できるようにさらに最適化できます。したがって、スペースを節約するために f[2][m] を定義するだけで済みます。

総時間の複雑さは O(n*m*maximum_shares_sell_per_day) です。

おそらく、時間を節約するためにさらに最適化できます。どんなフィードバックでも大歓迎です

于 2013-01-03T05:04:13.873 に答える