ダイナミックプランニング(2)-完全リュック【テンプレート】
945 ワード
問題の説明
N種類の品物とV容量のリュックサックがあり、それぞれの品物には無限のものがあります.i番目のアイテムを入れるのにかかるスペースはC[i]で、得られる価値はW[i]です.解:どのような物品を入れます
リュックサックは、これらの物品の消費空間の合計がリュックサックの容量を超えず、価値の合計が最大になるようにすることができます.
基本的な考え方
依然として解01リュックサックの時の構想に従って、F[i;v]に前のi種類の物品がちょうど1つの容量vの
リュックサックの最大の重み.状態遷移方程式は、各アイテムの異なるポリシーに従って書くことができます.
このように:
F[i,v] = max { F[i - 1,v - kC[ i ] ] + kW[ i ] | 0 ≤ kC[ i ] ≤ v }
これは01バックパック問題と同様にO(V N)個の状態を解く必要があるが,各状態を解く時間は定数ではなく,状態F[i,v]を解く時間はO(v/C[i]),全体の複雑さはO(NVΣV/C[i])と考えられ,比較的大きい.01リュックサック問題の基本構想を改善し,このような明確な方法を得た.これは01リュックサック問題の方程式が確かに重要であり,他のタイプのリュックサック問題を推し進めることができることを示している.しかし、私たちはやはりこの複雑さを改善しようとします.
O(VN)のアルゴリズム
N種類の品物とV容量のリュックサックがあり、それぞれの品物には無限のものがあります.i番目のアイテムを入れるのにかかるスペースはC[i]で、得られる価値はW[i]です.解:どのような物品を入れます
リュックサックは、これらの物品の消費空間の合計がリュックサックの容量を超えず、価値の合計が最大になるようにすることができます.
基本的な考え方
依然として解01リュックサックの時の構想に従って、F[i;v]に前のi種類の物品がちょうど1つの容量vの
リュックサックの最大の重み.状態遷移方程式は、各アイテムの異なるポリシーに従って書くことができます.
このように:
F[i,v] = max { F[i - 1,v - kC[ i ] ] + kW[ i ] | 0 ≤ kC[ i ] ≤ v }
これは01バックパック問題と同様にO(V N)個の状態を解く必要があるが,各状態を解く時間は定数ではなく,状態F[i,v]を解く時間はO(v/C[i]),全体の複雑さはO(NVΣV/C[i])と考えられ,比較的大きい.01リュックサック問題の基本構想を改善し,このような明確な方法を得た.これは01リュックサック問題の方程式が確かに重要であり,他のタイプのリュックサック問題を推し進めることができることを示している.しかし、私たちはやはりこの複雑さを改善しようとします.
O(VN)のアルゴリズム
<span style="font-size:18px;">for(int i = 0; i < n - 1; i++)
for(int j = C[i]; j <= v; j++)
dp[j] = max(dp[j], dp[j-C[i]] + W[i]);
// i j V
//C[i] W[i] </span>