ダイナミックプランニング——リュック問題P 02——完全リュック
2548 ワード
【概要】
完全リュック問題もかなり基礎的なリュック問題であり,2つの状態遷移方程式があり,それぞれ「基本構想」および「O(VN)アルゴリズム」の小節で与えられる.
【テーマ】
N種類の品物とV容量のリュックサックがあり、それぞれの品物には無限のものがあります.i番目のアイテムのボリュームはw[i]、価値はc[i]です.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
【基本的な考え方】
この問題は01リュックサックの問題によく似ていますが、それぞれのものには無限のものがあります.つまり、それぞれのアイテムの観点から考えると、それに関連する戦略はすでに2つを取るか取らないかではなく、0つを取るか、1つを取るか、2つを取るか…など多くの種類があります.
解01リュックサックの考え方に従えば、f[i][v]は、前のi種類の物品がv容量のリュックサックの最大の重み値を適切に入れることを示す.f[i][v]=max{f[i-1][v-k*w[i]+k*c[i]}(0<=k*w[i]<=v)
これは01バックパック問題と同様にO(N*V)個の状態を解く必要があるが,各状態を解く時間は定数ではなく,状態f[i][v]を解く時間はO(v/w[i])であり,全体の複雑度はO(VN)を超える.
01リュックサック問題の基本構想を改善し,このような明確な方法を得た.これは01リュックサック問題の方程式が確かに重要であり,他のタイプのリュックサック問題を推し進めることができることを示している.しかし、私たちはやはりこの複雑さを改善しようとしています.
【シンプルで効率的な最適化】
2つの物品i,jがw[i]<=w[j]を満たし、c[i]>=c[j]であれば、物品jを除去し、考慮しない.
原因:いかなる場合でも価値の小さい費用をjより高く、安価なiに変えることができ、少なくともこれ以上悪くない案を得ることができる.ランダムに生成されたデータに対して,この方法は往々にして物品の件数を大幅に減少させ,速度を速める.しかし、これは最悪の状況の複雑さを改善することはできません.特別に設計されたデータが1つのものも落ちない可能性があるからです.
この最適化は簡単なO(N^2)で実現でき,一般に耐えられる.
また、リュックサックの問題に対して、まずVより費用が大きいものを取り除き、それから類似のカウント順を用いて、費用が同じものの中で最も価値が高いものがどれなのかを計算し、O(V+N)でこの最適化を完成させるのが良い方法です.
【01バックに変換問題解決】
01リュック問題が最も基本的なリュック問題である以上、完全リュック問題を01リュック問題に変換して解くことを考えることができます.
最も簡単なアイデアは、i番目のアイテムがV/w[i]件まで選択されることを考慮して、i番目のアイテムをV/w[i]件の費用と価値が変わらないアイテムに変換し、この01リュックの問題を解くことです.
このように基本的な考え方を改善する時間の複雑さはありませんが、これは私たちに完全なリュックサック問題を01リュックサック問題に変換する考え方を与えました:1つの物品を複数の物品に分解します.
より効率的な変換方法は、i番目の物品をw[i]*2^k、価値c[i]*2^kのいくつかの物品に分解し、kはw[i]*2^k<=Vを満たす.
原因:これはバイナリの思想で、最良の策略がいくつかのi番目の物品を選ぶに関わらず、いつもいくつかの2^k件の物品の和に表すことができます.このように各アイテムをO(log(V/w[i]))アイテムに分解することは、大きな改良である.
【O(VN)のアルゴリズム】
このアルゴリズムは1次元配列を用いる
ぎじふごう
この擬似コードとP 01の擬似コードはvのループ順序だけが異なることがわかります.どうしてこのように改めればいいのですか.
まず,P 01ではv=V..0の逆順でループする理由を考える.これは、i回目のループにおける状態f[i][v]が状態f[i-1][v-w[i]]によって繰返しられることを保証するためである.言い換えれば、これは、1つのアイテムごとに1回だけ選択することを保証するためであり、「i番目のアイテムを選択する」という戦略を考慮する際に、i番目のアイテムを選択したサブ結果f[i-1][v-w[i]]が絶対にないことを保証するためである.現在、完全リュックサックの特徴は、各アイテムが無限に選択できることであるため、「i番目のアイテムを追加する」という戦略を考えるには、i番目のアイテムが選択可能なサブ結果f[i][v-w[i]]が必要であるため、v=0を採用する必要がある.Vのシーケンスサイクル.これがこの簡単なプログラムがなぜ成立したのか.
このアルゴリズムは別の考え方でも得られる.
例えば,基本構想における状態遷移方程式は,f[i][v]=max{f[i-1][v],f[i][v-w[i]+c[i]}と等価に形成できる.
この方程式を1次元配列で実現すると,上の擬似コードが得られる.
最後に、完全なリュックサック類を処理するプロセスの偽コードを抽象化します.
完全リュック問題もかなり基礎的なリュック問題であり,2つの状態遷移方程式があり,それぞれ「基本構想」および「O(VN)アルゴリズム」の小節で与えられる.
【テーマ】
N種類の品物とV容量のリュックサックがあり、それぞれの品物には無限のものがあります.i番目のアイテムのボリュームはw[i]、価値はc[i]です.リュックサックにどのアイテムを入れるかを解くと、これらのアイテムの費用の合計がリュックサックの容量を超えず、価値の合計が最大になります.
【基本的な考え方】
この問題は01リュックサックの問題によく似ていますが、それぞれのものには無限のものがあります.つまり、それぞれのアイテムの観点から考えると、それに関連する戦略はすでに2つを取るか取らないかではなく、0つを取るか、1つを取るか、2つを取るか…など多くの種類があります.
解01リュックサックの考え方に従えば、f[i][v]は、前のi種類の物品がv容量のリュックサックの最大の重み値を適切に入れることを示す.f[i][v]=max{f[i-1][v-k*w[i]+k*c[i]}(0<=k*w[i]<=v)
これは01バックパック問題と同様にO(N*V)個の状態を解く必要があるが,各状態を解く時間は定数ではなく,状態f[i][v]を解く時間はO(v/w[i])であり,全体の複雑度はO(VN)を超える.
01リュックサック問題の基本構想を改善し,このような明確な方法を得た.これは01リュックサック問題の方程式が確かに重要であり,他のタイプのリュックサック問題を推し進めることができることを示している.しかし、私たちはやはりこの複雑さを改善しようとしています.
【シンプルで効率的な最適化】
2つの物品i,jがw[i]<=w[j]を満たし、c[i]>=c[j]であれば、物品jを除去し、考慮しない.
原因:いかなる場合でも価値の小さい費用をjより高く、安価なiに変えることができ、少なくともこれ以上悪くない案を得ることができる.ランダムに生成されたデータに対して,この方法は往々にして物品の件数を大幅に減少させ,速度を速める.しかし、これは最悪の状況の複雑さを改善することはできません.特別に設計されたデータが1つのものも落ちない可能性があるからです.
この最適化は簡単なO(N^2)で実現でき,一般に耐えられる.
また、リュックサックの問題に対して、まずVより費用が大きいものを取り除き、それから類似のカウント順を用いて、費用が同じものの中で最も価値が高いものがどれなのかを計算し、O(V+N)でこの最適化を完成させるのが良い方法です.
【01バックに変換問題解決】
01リュック問題が最も基本的なリュック問題である以上、完全リュック問題を01リュック問題に変換して解くことを考えることができます.
最も簡単なアイデアは、i番目のアイテムがV/w[i]件まで選択されることを考慮して、i番目のアイテムをV/w[i]件の費用と価値が変わらないアイテムに変換し、この01リュックの問題を解くことです.
このように基本的な考え方を改善する時間の複雑さはありませんが、これは私たちに完全なリュックサック問題を01リュックサック問題に変換する考え方を与えました:1つの物品を複数の物品に分解します.
より効率的な変換方法は、i番目の物品をw[i]*2^k、価値c[i]*2^kのいくつかの物品に分解し、kはw[i]*2^k<=Vを満たす.
原因:これはバイナリの思想で、最良の策略がいくつかのi番目の物品を選ぶに関わらず、いつもいくつかの2^k件の物品の和に表すことができます.このように各アイテムをO(log(V/w[i]))アイテムに分解することは、大きな改良である.
【O(VN)のアルゴリズム】
このアルゴリズムは1次元配列を用いる
ぎじふごう
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-weight]+cost}この擬似コードとP 01の擬似コードはvのループ順序だけが異なることがわかります.どうしてこのように改めればいいのですか.
まず,P 01ではv=V..0の逆順でループする理由を考える.これは、i回目のループにおける状態f[i][v]が状態f[i-1][v-w[i]]によって繰返しられることを保証するためである.言い換えれば、これは、1つのアイテムごとに1回だけ選択することを保証するためであり、「i番目のアイテムを選択する」という戦略を考慮する際に、i番目のアイテムを選択したサブ結果f[i-1][v-w[i]]が絶対にないことを保証するためである.現在、完全リュックサックの特徴は、各アイテムが無限に選択できることであるため、「i番目のアイテムを追加する」という戦略を考えるには、i番目のアイテムが選択可能なサブ結果f[i][v-w[i]]が必要であるため、v=0を採用する必要がある.Vのシーケンスサイクル.これがこの簡単なプログラムがなぜ成立したのか.
このアルゴリズムは別の考え方でも得られる.
例えば,基本構想における状態遷移方程式は,f[i][v]=max{f[i-1][v],f[i][v-w[i]+c[i]}と等価に形成できる.
この方程式を1次元配列で実現すると,上の擬似コードが得られる.
最後に、完全なリュックサック類を処理するプロセスの偽コードを抽象化します.
procedure CompletePack(cost,weight)
for v=weight..V
f[v]=max{f[v],f[v-weight]+cost