配列内の高さを持つ n Trees が与えられます。そして、収集する必要がある木材の値 k units が与えられます。任意の高さの斧を持つことができますが、選択したときに使用できる斧は 1 つだけです。
使用する斧の最適な高さと、無駄を最小限に抑えるために伐採する木を教えてください。
高さ X の斧で高さ H の木を切った場合。H>X の場合、HX の木材が得られます。それ以外の場合は 0 の木材になります。
私はこの問題を試してみましたが、かなり悪い複雑さであるブルートフォースとは別に考えることができません。
以下のクエリの更新:- 斧の高さが 0 の場合、木の高さが 2,4 で k が 5 の場合、無駄が 0 になる必要はありません。これでクエリが明確になることを願っています。
上記の場合、斧の高さは 0 で、5 単位の木を得るには 2 本の木を切る必要があります。無駄は最小化する必要がある1ユニットになり、ここでは最小です
force などの他のパラメーターは必要ありません。
Subset sumは、NP 完全問題であり、与えられた斧の高さに対して最適な木のセットを選択する問題に還元できます。問題のその部分は NP 困難であり、最もよく知られているアルゴリズムは指数関数的に複雑です。
[2013 年 12 月 9 日編集: 最後の文の数式を修正!]
斧の高さを選択して、この高さを超える木をすべて伐採しても廃棄物がゼロになるようにすることは常に可能です。
これを確認するには、高さの降順に木を並べ替え、最も高い木のてっぺんから斧の高さを徐々に下げることを検討してください。一番高い木の高さが h だとします。関数に注意してください
f(x) = total amount of wood cut by using an axe of height h - x to
chop all trees of at least this height
は x = 0 のときに 0 から始まり、x の区分的に増加する線形関数であり、不連続性はありません。1 つまたは複数のツリーが切断可能になり始めるポイントを超えて x が増加するたびに、f(x) の変化率が増加しますが、これは問題を引き起こしません。したがって、木材 y の任意のレベルに対して、(概念的に) 高さ y の水平線をグラフ f(x) と交差させ、この点から x 軸まで垂直線を下ろしてその値を求めます。(プログラムで実際にこれを行う方法は演習として残しておきますが、ここにヒントがあります。木を高さの順序で降順で考えて、隣接する x 値 x1、x2 のペアを見つけ、h - x1 で切り刻んでも木が少なすぎるようにします。 h - x2 生成量が多すぎます。)