ダイナミックプランニング0-1リュック問題
1263 ワード
問題の説明:
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)ji第iの物品の重量がリュックサックの容量より大きい場合、人の前iの物品を詰める最大価値と、前i-1の物品を入れる最大価格は同じであり、すなわち物品iがリュックサックに入れられない
V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi)}j>wi 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)ji第iの物品の重量がリュックサックの容量より大きい場合、人の前iの物品を詰める最大価値と、前i-1の物品を入れる最大価格は同じであり、すなわち物品iがリュックサックに入れられない
V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi)}j>wi i番目の物品の重量がリュックサックの容量よりも小さい場合、(a)i番目の物品をリュックサックに入れると、リュックサック物品の価値はi-1番目の物品が容量位j-wiのリュックサックに入れる価値にi番目の物品の価値viを加える.(b)i番目の物品がリュックサックに入れられていない場合、リュックサックにおける物品価値は、前のi−1個の物品を容量jのリュックサックに入れて得られた価値に等しい.明らかに,両者の中で最も価値のあるのは,前のi個の物品を容量jのリュックサックに入れる最適解である.
コード:
#include
using namespace std;
int findMaxValue(int weight[],int value[],int n,int m){
int res;
int a[n+1][m+1];
for(int i=0;i>n>>m;
int weight[n];
int value[n];
for(int i=0;i>weight[i]>>value[i];
cout<