2

私はクラスの 1 つで頭の体操としてこれを尋ねられましたが、それを理解することができませんでした (宿題の質問ではなく、TA の 1 人が私たちに考えさせた単なる頭の体操でした)。

たとえば [1,5,11] で切断する n 個の点のリストと、たとえば 20 などの棒の全長を含む棒が与えられます。棒を切断する費用は同等であるとも言われます。ロッドの長さまで。与えられたすべてのカットでロッドをカットする最小コストと、最適なコストにつながるそれらのカットの順序を見つけたいと考えています。

たとえば、長さ 20 の棒を位置 5 で切断するには、20 ドルかかり、長さ 5 と長さ 15 の 2 つの丸太ができあがります。

または、別の例では、長さ 25 のロッドを位置 5 で切断し、次に位置 10 で切断すると、位置 5 で切断するのに $25 の費用がかかり、長さ 5 のロッドと長さ 20 のロッドが残り、費用がかかります。 10 位でカットするためにさらに 20 ドルを支払うと、2 つのポジションでカットする合計コストは 45 ドルになります。ただし、ロッドを 10 の位置で切断し、次に 5 の位置で切断すると、25 ドル + 10 ドル = 35 ドルの費用がかかります。

最後に、私たちはしたいですreturn the minimum cost of cutting the rod at all the given cuts and the sequence of those cuts that would lead to the optimal cost.

この問題の再帰的な解決策を考え出そうとしましたが、手ぶらで解決し続けました。考え？どんな助けでも大歓迎です。ありがとう！

4

2 に答える 2

1

ロッド切断問題のポイントは、貪欲なアルゴリズムが常に最適なソリューションを生成するとは限らないということだと私は信じています - この変種は同じポイントを証明しているようです.

L=50 のロッドを で切断するとし[13,25,26]ます。中間点に最も近いカットを選択するアルゴリズムは[25, 13, 26]、総コスト で行うように指示します50 + 25 + 25 = 100。[26, 13, 25]の合計コストでこれを改善でき50 + 26 + 13 = 89ます。

編集：

すなわち。でL=50ロッドをカットすると、それ以上カットする必要のないロッドと でカットする必要のあるロッドができます。次に、 でロッドをカットすると、1 本のロッドはそれ以上カットする必要がなくなり、2 番目のロッドは で最終カットが必要になります。次に最終的なカットを行い、各段階でカットされたロッドの長さの合計がコストになります ( )。P=26L=24 (P=26->50)L=26 (P=0->26)[25,13]L=26P=13L=13 (P=0->13)L=13 (P=13->26)P=2550 + 26 + 13

通常提案される代替案はトップダウンとボトムアップの手法であり、これらの効率は通常、関連するロジックに依存します (販売コストを最大化しようとする従来のロッド切断問題では、ボトムアップが再帰的コストを削減するため好まれます)呼び出します)。

于 2013-02-05T04:12:54.093 に答える