0

これが私が見つけた非常に興味深いJavaの問題です：

本の印刷が見つかる前に、本は「作家」と呼ばれる特定の人々によってコピーされました。簿記係はコピーする必要があるN冊の本のスタックを持っています。その目的のために彼はK人の作家を持っています。各本は異なるページ数を持つことができ、すべての作家はスタックの一番上からのみ本をとることができます（彼が本1をとる場合、彼は本2をとることができますが、本4または本5をとることはできません）。簿記係は各本のページ数を知っているので、作家がコピーしなければならない最大ページ数を可能な限り少なくするために、作家間で本を共有する必要があります。もちろん、ページを分割することはできません。 30ページの本を15と15に分割することはできません。

たとえば、3人の作家がいる7冊の本があり、それに応じて本のページがある場合：30 50 5 60 90 5 80最適な解決策は、最初の作家が最初の4冊、2番目の作家が次の本、3番目が最後の2冊の本なので、次のようになります。

1番目=145ページ
2番目=90ページ
3番目=85ページ

したがって、プログラムは、ライター間でページを共有するための最適なソリューションを見つけるアルゴリズムを作成することです。したがって、プログラムの最後に、それぞれが何ページを取得したかを示す必要があります。

これは何年も前のプログラミングコンテストでした。試してみたかったのですが、これまでに見つけたのは、すべての本の総ページ数を、取得したライターの数で割ると、例106.66ページの場合、スタックからその数に最も近い連続した本を各ライターに渡そうとしますが、特に本のページ数が合計を超える場合は、ページ数が多い場合はまったく機能しません。ページ数をライター数で割った値

ですから、あなたの意見を共有し、数学的なものなど、必要に応じてヒントやヒントを提供してください。これは非常に興味深いアルゴリズムです。

4

4 に答える 4

1

おそらくあまり効率的ではありませんが、ロジックは機能します。基本的に、本の数と同じ数の作家の数から始めて、作家の数になるまで減らします。

例を示します。7 つの値 30 50 5 60 90 5 80 から始めるとします。各ステップで、「最低のペア」を合計して値を 1 減らします。太字の値は、次の反復に引き継がれるペアです。

7
30 50 5 60 90 5 80
6
30 55 60 90 5 80
5
30 55 60 90 85
4
85 60 90 85
3
145 90 85

いくつかの疑似プログラミングを使用して、この例はそれを実装する方法を示しています

main(books: { 30 50 5 60 90 5 80 }, K: 3)

define main(books, K)
  writers = books
  while writers.length > K do
    reduceMinimalPair(writers)
  endwhile
end

define reduceMinimalPair(items)
  index = 0
  minvalue = items[0] + items[1]
  for i in 1..items.length-1 do
    if items[i] + items[i + 1] < minvalue then
      index = i
      minvalue = items[i] + items[i + 1]
    endif
  endfor
  items.removeat(index)
  items.removeat(index + 1)
  items.insertat(index, minvalue)
end
于 2012-04-28T20:08:39.287 に答える
1

b1、b2、...、bn ページの本 1...n があるとします。K 人のライターがいるとします。

行列 F[1...n,1...K]=無限大を初期化します。

F[i,1]= sum_j=1..i (bj) とする

ここで、k=2..K ごとに

F[i,k] = min_j=1..i( max(F[j,k-1], sum_r=j+1..i (br) )

于 2012-04-28T18:06:47.603 に答える
0

動的計画法でそれを解決する代わりに、誰もがこのページ数を超えてコピーしないというページの上限を二分探索することもできます。この数が収束するとき、それが答えです。

于 2012-04-28T18:54:10.777 に答える
0

あなたの考えは正しいと思いますが、大きな数ではうまくいかなかったと言っている場合は、平均よりも大きな数が存在するかどうかを確認し、その場合は別のことを行う必要があります。たぶん、番号を削除して、最初から作家かそれらの線に沿った何かにそれを与えてください

于 2012-04-28T17:56:47.167 に答える