0-1リュックサックアルゴリズム
1573 ワード
問題の説明:
Nの中の品物とリュックサックを1つ与えます.アイテムiの重量はWiで、その価値ビットVi、リュックサックの容量はCです.リュックサックに入ったものをどのように選択すれば、リュックサックに入ったものの総価値が最大になるのでしょうか.
物品を選択する際、各物品iには、リュックサックに入れるか、リュックサックに入れないかの2つの選択しかない.物iを複数回入れたり、物の一部だけ入れたりすることはできません.そのため、この問題は0-1リュックサック問題と呼ばれている.
問題の分析:
V(i,j)に、前i(1<=i<=n)個の物品にj(1<=j<=C)の容量のリュックサックに入れることができる物品の最大価値を示すと、以下の動的計画関数が得られる.
(1) V(i,0)=V(0,j)=0
(2) V(i,j)=V(i-1,j) j V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式は、i番目の物品の重量がリュックサックの容量より大きい場合、人を入れる前のi個の物品が得た最大価値と、前のi−1個の物品が得た最大価格は同じであり、すなわち、物品iがリュックサックに入れられないことを示す.第(2)の式は、第iの物品の重量がリュックサックの容量より小さい場合、(a)第iの物品をリュックサックに入れると、リュックサックの物品の価値は第i-1の物品が容量位j-wiのリュックサックに入れる価値に第iの物品の価値viを加えることに等しい.(b)i番目の物品がリュックサックに入れられていない場合、リュックサックにおける物品価値は、前のi−1個の物品を容量jのリュックサックに入れて得られた価値に等しい.明らかに,両者の中で最も価値のあるのは,前のi個の物品を容量jのリュックサックに入れる最適解である.
Nの中の品物とリュックサックを1つ与えます.アイテムiの重量はWiで、その価値ビットVi、リュックサックの容量はCです.リュックサックに入ったものをどのように選択すれば、リュックサックに入ったものの総価値が最大になるのでしょうか.
物品を選択する際、各物品iには、リュックサックに入れるか、リュックサックに入れないかの2つの選択しかない.物iを複数回入れたり、物の一部だけ入れたりすることはできません.そのため、この問題は0-1リュックサック問題と呼ばれている.
問題の分析:
V(i,j)に、前i(1<=i<=n)個の物品にj(1<=j<=C)の容量のリュックサックに入れることができる物品の最大価値を示すと、以下の動的計画関数が得られる.
(1) V(i,0)=V(0,j)=0
(2) V(i,j)=V(i-1,j) j V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式は、i番目の物品の重量がリュックサックの容量より大きい場合、人を入れる前のi個の物品が得た最大価値と、前のi−1個の物品が得た最大価格は同じであり、すなわち、物品iがリュックサックに入れられないことを示す.第(2)の式は、第iの物品の重量がリュックサックの容量より小さい場合、(a)第iの物品をリュックサックに入れると、リュックサックの物品の価値は第i-1の物品が容量位j-wiのリュックサックに入れる価値に第iの物品の価値viを加えることに等しい.(b)i番目の物品がリュックサックに入れられていない場合、リュックサックにおける物品価値は、前のi−1個の物品を容量jのリュックサックに入れて得られた価値に等しい.明らかに,両者の中で最も価値のあるのは,前のi個の物品を容量jのリュックサックに入れる最適解である.
#include
#include
int V[200][200];// i j
int KnapSack(int n,int w[],int v[],int x[],int C)
{
int i,j;
for(i=0;i<=n;i++)
V[i][0]=0;
for(j=0;j<=C;j++)
V[0][j]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=C;j++)
if(j=0;i--)
{
if(V[i][j]>V[i-1][j])
{
x[i]=1;
j=j-w[i];
}
else
x[i]=0;
}
printf(" :
");
for(i=0;i